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 (there is no remainder). The method can also be used to compute the determinant of matrices with (approximated) real entries, avoiding the introduction of any round-off errors beyond those already present in the input.

The definition of the determinant of a matrix involves only the operations of multiplication, addition and subtraction. Therefore the determinant of a matrix is an integer whenever all the entries are integers. However, actual computation of the determinant using the definition or Leibniz formula is impractical, as it requires O(n!) operations. Gaussian elimination has O(n³) complexity, but introduces division, which results in round-off errors when implemented using floating point numbers.

Round-off errors can be avoided if all the numbers are kept as integer fractions instead of floating point. But then the size of each element grows in size exponentially with the number of rows.^[1]

Bareiss brings up a question of performing an integer-preserving elimination while keeping the magnitudes of the intermediate coefficients reasonably small. Two algorithms are suggested:^[2][3]

1. Division-free algorithm — performs matrix reduction to triangular form without any division operation.
2. Fraction-free algorithm — uses division to keep the intermediate entries smaller, but due to the Sylvester's Identity the transformation is still integer-preserving (the division has zero remainder).

For completeness Bareiss also suggests fraction-producing multiplication-free elimination methods.^[2]

The program structure of this algorithm is a simple triple-loop, as in the standard Gaussian elimination. However in this case the matrix is modified so that each M_k,k entry contains the leading principal minor [M]_k,k. Algorithm correctness is easily shown by induction on k.^[4]

Si la suposición sobre los menores principales resulta ser falsa, por ejemplo, si M _{k − 1, k − 1} = 0 y algún M _{i , k − 1} ≠ 0 ( i = k ,..., n ) entonces podemos intercambiar la fila k − 1 con la fila i y cambiar el signo de la respuesta final.

Durante la ejecución del algoritmo de Bareiss, cada entero calculado es el determinante de una submatriz de la matriz de entrada. Esto permite, mediante la desigualdad de Hadamard , acotar el tamaño de estos enteros. Por lo demás, el algoritmo de Bareiss puede considerarse una variante de la eliminación gaussiana y requiere aproximadamente el mismo número de operaciones aritméticas.

De ello se deduce que, para una matriz n × n de valor máximo (absoluto) 2 ^L para cada entrada, el algoritmo de Bareiss se ejecuta en O( n ³ ) operaciones elementales con un límite de O( n ^{n /2}  2 ^nL ) en el valor absoluto de los valores intermedios necesarios. Su complejidad computacional es, por lo tanto, O( n ⁵ L ²  (log( n ) ²  + L ² )) cuando se utiliza aritmética elemental o O( n ⁴ L (log( n ) + L ) log(log( n ) + L ))) mediante multiplicación rápida .       

El algoritmo de Bareiss no se usa comúnmente para matrices de enteros, porque la aritmética multimodular permite una complejidad similar a la del algoritmo de Bareiss con multiplicación rápida, y es mucho más sencillo de implementar.

Por otro lado, el algoritmo de Bareiss puede utilizarse con entradas en cualquier dominio integral equipado con un algoritmo de división exacta y, en particular, para matrices de polinomios.