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 opérations. L'élimination de Gauss est de complexité , 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.
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. (Présente plus clairement la séquence des opérations.) : 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', 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.
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 contienne le mineur principal dominant . La correction de l'algorithme s'établit aisément par récurrence sur .
Entrée : , une matrice carrée d'ordre , dont on suppose tous les mineurs principaux dominants non nuls. Poser (remarque : est une variable auxiliaire). Pour allant de 1 à : Pour allant de à : Pour allant de à : Poser Poser Sortie : la matrice est modifiée en place ; chaque coefficient contient le mineur principal dominant , et le coefficient contient le déterminant de la matrice initiale.
Si l'hypothèse sur les mineurs principaux se révèle fausse — par exemple si alors qu'il existe pour un certain — il suffit d'échanger la ligne et la ligne , 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' 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 dont chaque coefficient est de valeur absolue au plus , l'algorithme de Bareiss s'exécute en opérations élémentaires, la valeur absolue des grandeurs intermédiaires étant bornée par . Sa complexité est donc avec l'arithmétique élémentaire, ou en recourant à un algorithme de multiplication rapide.
Utilisation L'algorithme de Bareiss est peu employé pour les matrices à coefficients entiers, car l' 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
Voir aussi Bibliographie
Articles connexes Déterminant (mathématiques) Élimination de Gauss-Jordan Calcul formel
Liens externes 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
Catégorie:Algèbre linéaire Catégorie:Calcul formel Catégorie:Algorithmique