En matemáticas, el algoritmo de Bareiss , llamado así en honor a Erwin Bareiss, es un algoritmo para calcular el determinante o la forma escalonada de una matriz con entradas enteras utilizando únicamente aritmética de enteros; Se garantiza que cualquier división que se realice será exacta (no hay resto ). El método también se puede utilizar para calcular el determinante de matrices con entradas reales (aproximadas) , evitando la introducción de errores de redondeo más allá de los que ya están presentes en la entrada.
El algoritmo fue anunciado originalmente por Jack Edmonds en 1966 y publicado en 1967.[1] El algoritmo general de Bareiss es distinto del algoritmo de Bareiss para matrices de Toeplitz .
En algunos países de habla hispana, este algoritmo también se conoce como Bareiss-Montante , en honor a René Mario Montante Pardo, profesor de la Universidad Autónoma de Nuevo León , México , quien popularizó el método entre sus alumnos.
La definición de determinante solo tiene operaciones de multiplicación, suma y resta. Obviamente el determinante es un número entero si todas las entradas de la matriz son números enteros. Sin embargo, el cálculo real del determinante utilizando la definición o la fórmula de Leibniz no es práctico, ya que requiere operaciones O ( n! ).
La eliminación gaussiana tiene una complejidad O( n 3 ), pero introduce división, lo que da como resultado errores de redondeo cuando se implementa utilizando números de punto flotante.
Los errores de redondeo se pueden evitar si todos los números se mantienen como fracciones enteras en lugar de coma flotante. Pero luego 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 números enteros manteniendo las magnitudes de los coeficientes intermedios razonablemente pequeñas. Se sugieren dos algoritmos: [2] [3]
Para completar, 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 triple bucle simple, como en la eliminación gaussiana estándar. Sin embargo, en este caso la matriz se modifica para que cada entrada M k,k contenga el principal menor principal [ M ] k,k . La corrección del algoritmo se demuestra fácilmente mediante inducción en k . [4]
Si la suposición sobre los menores principales resulta ser falsa, por ejemplo, si M k −1, k −1 = 0 y algo de M i , k −1 ≠ 0 ( i = k ,..., n ), entonces podemos intercambiar los k −1-ésima fila con la i -ésima fila y cambie el signo de la respuesta final.
Durante la ejecución del algoritmo de Bareiss, cada número entero que se calcula es el determinante de una submatriz de la matriz de entrada. Esto permite, utilizando la desigualdad de Hadamard , limitar el tamaño de estos números enteros. De lo contrario, el algoritmo de Bareiss puede verse como una variante de la eliminación gaussiana y necesita 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 3 ) operaciones elementales con un límite O( n n /2 2 nL ) en el valor absoluto. de valores intermedios necesarios. Su complejidad computacional es, por tanto, O( n 5 L 2 (log( n ) 2 + L 2 )) cuando se utiliza aritmética elemental o O( n 4 L (log( n ) + L ) log(log( n ) + L )) ) usando la multiplicación rápida .
