Algoritmul Bareis

Algoritmul Bareiss este un algoritm pentru calcularea determinantului sau a treptei unei matrice cu elemente întregi folosind aritmetica pur întregi. Numit după E. Bareys . Orice împărțire efectuată de algoritm garantează o împărțire exactă (fără rest ). Metoda poate fi folosită și pentru a calcula determinantul unei matrice cu elemente reale (aproximative) , ceea ce elimină erorile de rotunjire , cu excepția erorilor deja prezente în intrare.

Istorie

Algoritmul general al lui Bareis diferă de algoritmul cu același nume pentru inversarea matricelor Toeplitz .

În unele țări vorbitoare de spaniolă , algoritmul este cunoscut și sub numele de algoritmul Bareis-Monante , deoarece René Mario Montante Pardo, profesor la Universitatea Autonomă din Nuevo León din Mexic , a popularizat metoda în rândul studenților.

Prezentare generală

Definiția determinantului folosește numai operațiile de înmulțire, adunare și scădere . În mod evident, determinantul va fi întreg dacă toate elementele matricei sunt întregi. Cu toate acestea, calcularea efectivă a determinantului, fie pur din definiție, fie folosind formula lui Leibniz , este nepractică deoarece necesită operații. $O(n!)$

Metoda Gaussiană are complexitate , dar utilizează diviziunea, ceea ce duce la erori de rotunjire dacă este implementată cu aritmetică în virgulă mobilă . $O(n^{3})$

Erorile de rotunjire pot fi evitate prin stocarea tuturor numerelor ca fracții în loc de numere în virgulă mobilă. Cu toate acestea, dimensiunea fiecărui element crește exponențial în funcție de numărul de rânduri [1] .

Bareis a pus problema păstrării eliminărilor în numere întregi, păstrând în același timp valoarea coeficienților intermediari suficient de mică. Au fost propuși doi algoritmi [2] [3] :

Algoritm fără diviziune - reduce matricea la o formă triunghiulară fără nicio operație de divizare.
Algoritm fără resturi - folosește diviziunea pentru a reduce valorile intermediare, dar datorită identității Sylvester , transformarea rămâne întreagă (diviziunea are rest zero).

Pentru completitudine, Bareis a propus și metode de eliminare fără înmulțire, dar cu fracții [2] .

Algoritm

Structura de calcul a acestui algoritm este o buclă triplă simplă, ca în metoda obișnuită Gauss . Cu toate acestea, în acest caz, matricea este modificată astfel încât fiecare element să conțină un principal principal minor [M] k, k . Corectitudinea algoritmului este ușor de arătat prin inducție pe k [4] . $M_{k,k)$

Intrare: M este o matrice în baza ipotezei că toți minorii principali nu sunt zero. $n\ ori n$
$[M]_{k,k)$
Sa punem $M_{0,0}=1$
Pentru toți k de la 1 la n-1 :
- Pentru tot
i de la k+1 la n :
- Pentru toate
j de la k+1 la n :
- Sa punem $M_{i,j}={\frac {M_{i,j}M_{k,k}-M_{i,k}M_{k,j}}{M_{k-1,k-1 }}}$

Date de ieșire: Matricea este schimbată în loc ,
fiecare element M k, k conține principalul minor principal , valoarea conține determinantul matricei originale M.

[M]_{k,k)

M_{n,n)

Dacă presupunerea că principalii minori nu sunt egali cu zero se dovedește a fi incorectă, adică , iar unii sunt, atunci putem rearanja rândurile k-1 și i pe alocuri, schimbând semnul valorii finale. $M_{k-1,k-1}=0$ $M_{i,k-1}\neq 0(i=k,\dots,n)$

Analiză

În timpul execuției algoritmului Bareis, orice număr întreg calculat este determinantul unei submatrici a matricei de intrare. Acest lucru permite utilizarea inegalității Hadamard pentru a limita dimensiunea numerelor întregi. Altfel, algoritmul Bareis poate fi privit ca o variantă a metodei Gauss , care necesită practic același număr de operații aritmetice.

Rezultă că pentru o matrice cu o valoare maximă (absolută) pentru fiecare element, algoritmul Bareis rulează în O( n 3 ) operații elementare cu o constrângere asupra valorii absolute a valorilor intermediare. Complexitatea de calcul a algoritmului echivalează apoi cu utilizarea aritmeticii elementare sau utilizarea înmulțirii rapide . $n\ ori 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)))$

Note

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

Literatură

Middeke J., Jeffrey DJ, Koutschan C. Common Factors in Fraction-Free Matrix Decompositions // Math.Comput.Sci. - 2020. - doi : 10.1007/s11786-020-00495-9 .
Erwin H. Bareiss. Identitatea lui Sylvester și eliminarea gaussiană cu păstrarea întregului în mai mulți pași // Matematica calculului. - 1968. - T. 22 , nr. 103 . - S. 565-578 . - doi : 10.2307/2004533 . — .
Erwin H. Bareiss. Eliminare gaussiană cu păstrarea întregului în mai multe etape . - 1966. (Conține o descriere clară a secvenței operațiilor)
Chee Keng Yap. Probleme fundamentale ale algebrei algoritmice // Oxford University Press. — 2000.

Metode numerice ale algebrei liniare
Concepte cheie	Număr în virgulă mobilă • Robustețe de calcul
Sarcini	Sistem de ecuații algebrice liniare • Descompunerea matricei • Înmulțirea matricei ( algoritmi ) • Împărțirea matricei • Matrice rară
Suport hardware	Cache procesor • Buffer de traducere • Algoritmi insensibili la cache • SIMD • Multiprocesare
Software	MATLAB • BLAS • LAPACK • Compararea bibliotecilor liniare de alegbra • Compararea bibliotecilor de uz general