Algoritmo de Bareiss

En matemáticas, el algoritmo de Bareiss , que recibe su nombre de Erwin Bareiss , es un algoritmo para calcular el determinante o la forma escalonada de una matriz con entradas enteras utilizando únicamente aritmética entera; todas las divisiones realizadas son exactas (no hay resto ). El método también puede utilizarse para calcular el determinante de matrices con entradas reales (aproximadas) , evitando la introducción de errores de redondeo adicionales a los ya presentes en los datos de entrada.

La definición del determinante de una matriz solo involucra las operaciones de multiplicación, suma y resta. Por lo tanto, el determinante de una matriz es un número entero cuando todos sus elementos son enteros. Sin embargo, el cálculo real del determinante mediante la definición o la fórmula de Leibniz resulta poco práctico, ya que requiere O( n! ) operaciones. La eliminación gaussiana tiene una complejidad ^de O( n³ ), pero introduce la división, lo que genera errores de redondeo al implementarse con números de coma flotante.

Los errores de redondeo pueden evitarse si todos los números se mantienen como fracciones enteras en lugar de números de coma flotante. Pero entonces el tamaño de cada elemento crece exponencialmente con el número de filas. ^{[ 1 ]}

Bareiss plantea la cuestión de realizar una eliminación que preserve los enteros manteniendo las magnitudes de los coeficientes intermedios razonablemente pequeñas. Se sugieren dos algoritmos: ^{[ 2 ] [ 3 ]}

1. Algoritmo sin división: realiza la reducción de la matriz a forma triangular sin ninguna operación de división.
2. Algoritmo sin fracciones: utiliza la división para mantener las entradas intermedias más pequeñas, pero debido a la identidad de Sylvester, la transformación sigue conservando los números enteros (la división tiene resto cero).

Para mayor exhaustividad, Bareiss también sugiere métodos de eliminación sin multiplicación que producen fracciones. ^{[ 2 ]}

La estructura del programa de este algoritmo es un bucle triple simple, como en la eliminación gaussiana estándar. Sin embargo, en este caso la matriz se modifica de manera que cada entrada M _k,k contiene el menor principal [ M ] _k,k . La corrección del algoritmo se demuestra fácilmente por inducción sobre 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.