Accession Number : ADA313755

Title :   A Simplified Fraction-Free Integer Gauss Elimination Algorithm.

Descriptive Note : Final rept. Jun-Aug 95,

Corporate Author : NAVAL AIR WARFARE CENTER AIRCRAFT DIV PATUXENT RIVER MD

Personal Author(s) : Turner, Peter R.

PDF Url : ADA313755

Report Date : 05 AUG 1995

Pagination or Media Count : 28

Abstract : This paper presents a new version of Gauss elimination for integer arithmetic. This new algorithm allows fraction-free integer computation without requiring any calls to a greatest common divisor routine. It does however keep the growth in the integer dynamic range to a minimum. The algorithm is based on a careful comparison of the divisionless integer GE and the 'normal' algorithm using divisions within a floating-point or real arithmetic setting. From this analysis, we identify common factors which are necessarily present throughout the active part of the matrix. These can then be removed by exact integer division. A further consequence of this analysis is that the diagonal entries of the final upper triangular factor are precisely the determinants of the principal minors of the original matrix. In a parallel processing environment, the additional cost of these integer division is minimized since, at each stage, the whole active array is being divided by the same integer.

Descriptors :   *INTEGER PROGRAMMING, *FLOATING POINT OPERATION, ALGORITHMS, ARRAYS, PARALLEL PROCESSING, ELIMINATION, ARITHMETIC, DYNAMIC RANGE.

Subject Categories : Computer Programming and Software

Distribution Statement : APPROVED FOR PUBLIC RELEASE