Bareiss algorithm

In mathematics, the Bareiss algorithm, named after Erwin Bareiss, is an algorithm to calculate the determinant of a matrix with integer entries using only integer arithmetic; any divisions that are performed are guaranteed to be exact (there is no remainder). The method can also be used to compute the determinant of matrices with (approximated) real entries, avoiding the introduction any round-off errors beyond those already present in the input.

For an n × n matrix of maximum (absolute) value 2^L for each entry, the Bareiss algorithm runs in O(n³) elementary operations with an O(n ⁿ 2^nL) bound on the absolute value of intermediate values needed.

References

• Bareiss, Erwin (1968), "Sylvester's Identity and Multistep Integer-Preserving Gaussian Elimination" (PDF), Mathematics of computation, 22 (102): 565–578.

External links

• Yap, Chee, "Linear Systems", Fundamental Problems of Algorithmic Algebra