A Simplified Fraction-Free Integer Gauss Elimination Algorithm.

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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Aug 05, 1995
Accession Number
ADA313755

Entities

People

  • Peter R. Turner

Organizations

  • Naval Air Warfare Center

Tags

Communities of Interest

  • Air Platforms
  • Materials and Manufacturing Processes
  • Sensors
  • Weapons Technologies

DTIC Thesaurus Topics

  • Aerial Warfare
  • Aircrafts
  • Algorithms
  • Arithmetic
  • Computational Complexity
  • Computational Science
  • Computations
  • Detection
  • Dynamic Range
  • Elimination
  • Floating Point Operations
  • Linear Systems
  • Mathematics
  • Numbers
  • Numerical Analysis
  • Rational Numbers
  • United States Naval Academy

Readers

  • Linear Algebra
  • Operations Research