Algoritmo Bareis

El algoritmo de Bareiss es un algoritmo para calcular el determinante o escalar una matriz con elementos enteros usando aritmética puramente entera. El nombre de E. Bareys . Cualquier división realizada por el algoritmo garantiza una división exacta (sin resto ). El método también se puede utilizar para calcular el determinante de una matriz con elementos reales (aproximados) , lo que elimina los errores de redondeo , excepto los errores ya presentes en la entrada.

Historia

El algoritmo general de Bareis difiere del algoritmo del mismo nombre para invertir matrices de Toeplitz .

En algunos países de habla hispana, el algoritmo también se conoce como algoritmo Bareis-Monante , debido a que René Mario Montante Pardo, profesor de la Universidad Autónoma de Nuevo León en México , popularizó el método entre los estudiantes.

Resumen

La definición del determinante usa solo las operaciones de multiplicación, suma y resta . Obviamente, el determinante será entero si todos los elementos de la matriz son enteros. Sin embargo, calcular el determinante, ya sea puramente a partir de la definición o usando la fórmula de Leibniz , no es práctico porque requiere operaciones. ${\ estilo de visualización O (n!)}$

El método gaussiano tiene complejidad , pero usa división, lo que da como resultado errores de redondeo si se implementa con aritmética de punto flotante . $O(n^{3})$

Los errores de redondeo se pueden evitar almacenando todos los números como fracciones en lugar de números de punto flotante. Sin embargo, el tamaño de cada elemento crece exponencialmente dependiendo del número de filas [1] .

Bareis planteó la cuestión de mantener las eliminaciones en números enteros, manteniendo el valor de los coeficientes intermedios lo suficientemente pequeño. Se han propuesto dos algoritmos [2] [3] :

Algoritmo sin división: reduce la matriz a una forma triangular sin ninguna operación de división.
Algoritmo sin residuos: utiliza la división para reducir los valores intermedios, pero debido a la identidad de Sylvester , la transformación sigue siendo un número entero (la división tiene un residuo cero).

Para completar, Bareis también propuso métodos de eliminación sin multiplicación, pero con fracciones [2] .

Algoritmo

La estructura computacional de este algoritmo es un bucle triple simple, como en el método habitual de Gauss . Sin embargo, en este caso se modifica la matriz para que cada elemento contenga un principal principal menor [M] k, k . La corrección del algoritmo se muestra fácilmente por inducción en k [4] . ${\ Displaystyle M_ {k, k}}$

Entrada: M es una matriz bajo el supuesto de que todos los principales principales menores no son cero. $n\veces n$
${\ estilo de visualización [M] _ {k, k))$
Pongamos ${\ estilo de visualización M_ {0,0} = 1}$
Para todo k de 1 a n-1 :
- Para todo
i de k+1 a n :
- Para todo
j desde k+1 hasta n :
- Pongamos $M_{i,j}={\frac {M_{i,j}M_{k,k}-M_{i,k}M_{k,j}}{M_{k-1,k-1 }}}$

Datos de salida: La matriz se cambia de lugar ,
cada elemento M k, k contiene el menor principal principal , el valor contiene el determinante de la matriz original M.

{\ estilo de visualización [M] _ {k, k))

{\ Displaystyle M_ {n, n}}

Si la suposición de que los principales menores no son iguales a cero resulta incorrecta, es decir , y algunos lo son, entonces podemos reorganizar las filas k-1 e i en lugares, cambiando el signo del valor final. $M_{k-1,k-1}=0$ $M_{i,k-1}\neq 0(i=k,\dots,n)$

Análisis

Durante la ejecución del algoritmo de Bareis, cualquier número entero calculado es el determinante de una submatriz de la matriz de entrada. Esto permite usar la desigualdad de Hadamard para limitar el tamaño de los números enteros. De lo contrario, el algoritmo de Bareis puede verse como una variante del método de Gauss , que requiere prácticamente el mismo número de operaciones aritméticas.

De ello se deduce que para una matriz con un valor máximo (absoluto) para cada elemento, el algoritmo de Bareis se ejecuta en O( n 3 ) operaciones elementales con una restricción sobre el valor absoluto de los valores intermedios. La complejidad computacional del algoritmo equivale entonces a usar aritmética elemental o usar multiplicaciones rápidas . $n\veces n$ $2^{L}$ $O(n^{\tfrac {n}{2}}2^{nL})$ $O(n^{5}L^{2}(\log(n)^{2}+L^{2}))$ $O(n^{4}L(\log(n)+L)\log(log(n)+L)))$

Notas

↑ Middeke, Jeffrey, Koutschan, 2020 .
↑ 1 2 Bareiss, 1968 , pág. 565-578.
↑ Bareiss, 1966 .
↑ Yap, 2000 .

Literatura

Middeke J., Jeffrey DJ, Koutschan C. Factores comunes en descomposiciones de matrices sin fracciones // Math.Comput.Sci. -2020. - doi : 10.1007/s11786-020-00495-9 .
Erwin H. Bareiss. Identidad de Sylvester y eliminación gaussiana de conservación de enteros de varios pasos // Matemáticas de computación. - 1968. - T. 22 , núm. 103 . - S. 565-578 . -doi : 10.2307/ 2004533 . — .
Erwin H. Bareiss. Eliminación gaussiana de conservación de enteros de varios pasos . - 1966. (Contiene una descripción clara de la secuencia de operaciones)
Chee Keng Yap. Problemas fundamentales del álgebra algorítmica // Oxford University Press. — 2000.

Métodos numéricos de álgebra lineal
Conceptos clave	Número de punto flotante • Robustez computacional
Tareas	Sistema de ecuaciones algebraicas lineales • Descomposición de matrices • Multiplicación de matrices ( algoritmos ) • Desdoblamiento de matrices • Matriz dispersa
soporte de hardware	Caché del procesador • Búfer de traducción • Algoritmos insensibles a la caché • SIMD • Multiprocesamiento
Software	MATLAB • BLAS • LAPACK • Comparación de bibliotecas de álgebra lineal • Comparación de bibliotecas de propósito general