Bareiss algorithm
In mathematics, the Bareiss algorithm, named after Erwin Bareiss, is an algorithm to calculate the determinant or the echelon form of a matrix with integer entries using only integer arithmetic; any divisions that are performed are guaranteed to be exact. The method can also be used to compute the determinant of matrices with real entries, avoiding the introduction any round-off errors beyond those already present in the input.Analysis
During the execution of Bareiss algorithm, every integer that is computed is the determinant of a submatrix of the input matrix. This allows, using the Hadamard inequality, to bound the size of these integers. Otherwise, the Bareiss algorithm may be viewed as a variant of Gaussian elimination and needs roughly the same number of arithmetic operations.
It follows that, for an n × n matrix of maximum value 2L for each entry, the Bareiss algorithm runs in O elementary operations with an O bound on the absolute value of intermediate values needed. Its computational complexity is thus O when using elementary arithmetic or O) by using fast multiplication.History
The general Bareiss algorithm is distinct from the Bareiss algorithm for Toeplitz matrices.
In some Spanish-speaking countries, this algorithm is also known as Bareiss-Montante, because of René Mario Montante Pardo, a professor of the Universidad Autónoma de Nuevo León, Mexico, who popularized the method among his students.
