ARTIKELDIGITAL.COM

En mathématiques, l'algorithme de Bareiss, nommé d'après Erwin Bareiss, est un algorithme permettant de calculer le déterminant ou la forme échelonnée d'une matrice à coefficients entiers en n'utilisant que l'arithmétique entière : toutes les divisions effectuées sont garanties exactes (leur reste est nul). La méthode peut également servir à calculer le déterminant de matrices à coefficients réels (approchés), sans introduire d'erreur d'arrondi au-delà de celles déjà présentes dans les données d'entrée.

Principe

La définition du déterminant d'une matrice ne fait intervenir que des multiplications, des additions et des soustractions. Le déterminant d'une matrice est donc un entier dès lors que tous ses coefficients sont entiers. Cependant, le calcul effectif du déterminant à partir de la définition, ou de la formule de Leibniz, est impraticable puisqu'il requiert $O(n!)$ opérations. L'élimination de Gauss est de complexité $O(n 3)$ , mais elle introduit des divisions, sources d'erreurs d'arrondi lorsqu'elle est mise en œuvre en virgule flottante.

Ces erreurs d'arrondi peuvent être évitées en conservant tous les nombres sous forme de fractions d'entiers plutôt qu'en virgule flottante, mais la taille de chaque coefficient croît alors exponentiellement avec le nombre de lignes^[1].

Bareiss pose la question d'une élimination préservant le caractère entier des coefficients tout en maintenant l'ordre de grandeur des valeurs intermédiaires raisonnablement petit. Il propose deux algorithmes^[2]^,^[3] :

un algorithme sans division, qui réduit la matrice à une forme triangulaire sans aucune opération de division ;
un algorithme sans fraction, qui utilise la division pour maintenir les coefficients intermédiaires plus petits ; en vertu de l'identité de Sylvester (en), la transformation reste néanmoins à valeurs entières (la division est exacte).

Par souci d'exhaustivité, Bareiss propose également des méthodes d'élimination sans multiplication, qui produisent en revanche des fractions^[2].

Algorithme

La structure du programme se réduit à une triple boucle, comme pour l'élimination de Gauss classique. Ici cependant, la matrice est modifiée de telle sorte que chaque coefficient $M k,k$ contienne le mineur principal dominant $[M] k, k$ . La correction de l'algorithme s'établit aisément par récurrence sur $k$ ^[4].

Entrée : $M$ , une matrice carrée d'ordre $n$ , dont on suppose tous les mineurs principaux dominants $[M] k, k$ non nuls.
Poser $M 0,0 = 1$ (remarque : $M 0,0$ est une variable auxiliaire).
Pour k allant de 1 à n − 1 :
- Pour i allant de k + 1 à n :
  - Pour j allant de k + 1 à n :
    - Poser $M_{i,j}={\frac {M_{i,j}M_{k,k}-M_{i,k}M_{k,j}}{M_{k-1,k-1}}}$
  - Poser $M i, k = 0$
Sortie : la matrice est modifiée en place ; chaque coefficient $M k,k$ contient le mineur principal dominant $[M] k, k$ , et le coefficient $M n,n$ contient le déterminant de la matrice $M$ initiale.

Si l'hypothèse sur les mineurs principaux se révèle fausse — par exemple si $M k -1, k -1 = 0$ alors qu'il existe $M i, k -1 \neq 0$ pour un certain $i = k, \dots, n$ — il suffit d'échanger la ligne $k - 1$ et la ligne $i$ , puis de changer le signe du résultat final.

Analyse

Au cours de l'exécution de l'algorithme de Bareiss, chaque entier calculé est le déterminant d'une sous-matrice de la matrice d'entrée. L'inégalité d'Hadamard (en) permet ainsi de majorer la taille de ces entiers. Pour le reste, l'algorithme de Bareiss peut être vu comme une variante de l'élimination de Gauss et nécessite approximativement le même nombre d'opérations arithmétiques.

Il en découle que, pour une matrice $n \times n$ dont chaque coefficient est de valeur absolue au plus $2 L$ , l'algorithme de Bareiss s'exécute en $O (n 3)$ opérations élémentaires, la valeur absolue des grandeurs intermédiaires étant bornée par $O(n n /2 2 nL)$ . Sa complexité est donc $O(n 5 L 2 (log(n) 2 + L 2))$ avec l'arithmétique élémentaire, ou $O(n 4 L (log(n) + L) log(log(n) + L))$ en recourant à un algorithme de multiplication rapide.

Utilisation

L'algorithme de Bareiss est peu employé pour les matrices à coefficients entiers, car l'arithmétique multimodulaire (en) atteint une complexité comparable à celle de l'algorithme de Bareiss avec multiplication rapide, tout en étant bien plus simple à mettre en œuvre.

En revanche, l'algorithme de Bareiss s'applique à des coefficients pris dans n'importe quel anneau intègre muni d'un algorithme de division exacte, et en particulier aux matrices de polynômes.

Notes et références

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Bareiss algorithm » (voir la liste des auteurs).

↑ (en) J. Middeke, D. J. Jeffrey et C. Koutschan, « Common Factors in Fraction-Free Matrix Decompositions », Mathematics in Computer Science, vol. 15, n^o 4,‎ 2020, p. 589-608 (DOI 10.1007/s11786-020-00495-9, arXiv 2005.12380)
↑ ^{a et b} (en) Erwin H. Bareiss, « Sylvester's Identity and multistep integer-preserving Gaussian elimination », Mathematics of Computation, vol. 22, n^o 103,‎ 1968, p. 565-578 (DOI 10.2307/2004533, JSTOR 2004533, lire en ligne)
↑ (en) Erwin H. Bareiss, « Multistep integer-preserving Gaussian elimination », 1966. (Présente plus clairement la séquence des opérations.)
↑ (en) Chee Keng Yap, Fundamental Problems of Algorithmic Algebra, Oxford University Press, 2000

Voir aussi

Bibliographie

Lionel Ducos, « Algorithme de Bareiss, algorithme des sous-résultants », RAIRO Informatique théorique et applications, vol. 30, n^o 4,‎ 1996, p. 319-347 (lire en ligne)

Articles connexes

Liens externes

(en) Article original de Bareiss (1968), sur le site de l'American Mathematical Society
Article de Lionel Ducos (1996), dans RAIRO Informatique théorique et applications, disponible sur Numdam

[1] (en) J. Middeke, D. J. Jeffrey et C. Koutschan, « Common Factors in Fraction-Free Matrix Decompositions », Mathematics in Computer Science, vol. 15, n^o 4,‎ 2020, p. 589-608 (DOI 10.1007/s11786-020-00495-9, arXiv 2005.12380)

[bareiss-2] {a et b} (en) Erwin H. Bareiss, « Sylvester's Identity and multistep integer-preserving Gaussian elimination », Mathematics of Computation, vol. 22, n^o 103,‎ 1968, p. 565-578 (DOI 10.2307/2004533, JSTOR 2004533, lire en ligne)

[3] (en) Erwin H. Bareiss, « Multistep integer-preserving Gaussian elimination », 1966. (Présente plus clairement la séquence des opérations.)

[4] (en) Chee Keng Yap, Fundamental Problems of Algorithmic Algebra, Oxford University Press, 2000

[1]

[2]

[3]

[4]

Algorithme de Bareiss