Fraction Free Gaussian Elimination for Sparse Matrices

A variant of the fraction free form of Gaussian elimination is presented. This algorithm reduces the amount of arithmetic involved when the matrix has many zero entries. The advantage can be great for matrices with symbolic entries (integers, polynomials, expressions in trigonometric functions, etc.). These claims are supported with some analysis and experimental data. Let A be a n \Theta m matrix over an integral domain R. We will assume that the leading principal minors of A are nonzero. This assumption is not necessary, but simplifies the discussion by eliminating the issue of pivoting. First we offer a recursive description of Bareiss' standard fraction free Gaussian elimination [Bar68]. A (\Gamma1) 0;0 = 1; A (0) i;j = A i;j ; for 1 i n; 1 j m; A (k) i;j = A (k\Gamma1) k;k A (k\Gamma1) i;j \Gamma A (k\Gamma1) i;k A (k\Gamma1) k;j A (k\Gamma2) k\Gamma1;k\Gamma1 ; for 1 k ! n; k ! i n; k ! j m: It is well known that A (k) i;j = fi fi fi fi fi fi fi fi ..