Algorithmes pour les fonctions spéciales dans les algèbres de Ore

Support de cours algorithmes pour les fonctions spéciales dans les algèbres de Ore, tutoriel & guide de travaux pratiques algorithmes en pdf.

Algèbre linéaire dense : de Gauss à Strassen

Résumé
L’algèbre linéaire est au cœur de nombreux problèmes algorithmiques. La multiplication matricielle usuelle et la méthode du pivot de Gauss ont une complexité arithmétique cubique en la taille. Dans ce chapitre, nous montrons que pour la plupart des questions d’algèbre linéaire dense – multiplication, inversion, déterminant, résolution de système – il existe des algorithmes plus eﬃcaces, de complexité strictement sous-cubique.
Introduction
En mathématiques, il est de coutume de considérer qu’un problème est rendu trivial lorsqu’il est ramené à une question d’algèbre linéaire. Du point de vue cal-culatoire se pose cependant la question de l’eﬃcacité des opérations matricielles.
L’algorithmique des matrices : tentative de classification. Les problèmes algorithmiques en algèbre linéaire cachent des diﬃcultés très subtiles. En général, les premières questions que l’on est amené à se poser en rapport avec la manipulation des matrices concernent le calcul eﬃcace du produit matrice-matrice, du produit matrice-vecteur, de l’inverse, ainsi que la résolution de systèmes.
Les réponses à ces questions varient fortement selon le type de matrices considérées.
Une classification possible est la suivante.
Les matrices denses. Ce sont les matrices quelconques, sans aucune structure par-ticulière. Nous verrons que l’algorithmique des matrices denses peut se ramener essentiellement au produit matriciel, dont la complexité est une question extrême-ment délicate.
Les matrices creuses. Beaucoup de problèmes linéaires se formulent en termes de matrices possédant un nombre important d’éléments nuls, dites « creuses ». Dans ce cas, l’algorithmique dense est inappropriée ; il est possible de tirer parti de la forme creuse en utilisant des outils mieux adaptés, à base de récurrences linéaires.
Les matrices structurées. Enfin, il existe des familles de matrices particulières, souvent associées à des applications linéaires entre espaces de polynômes, telles que les matrices de type Sylvester pour le résultant, de type Vandermonde pour l’évaluation et l’interpolation, de type Toeplitz et Hankel pour l’approximation de Padé et de Padé-Hermite, etc . . . Pour ces types de matrices clairement identifiés, on développe soit une algorithmique ad hoc, soit une théorie unifiée reposant sur le concept de « rang de déplacement ».
Schématiquement, l’algorithmique des matrices denses est la plus lente, de com-plexité située entre O(n2) et O(n3), en taille n. La complexité du calcul avec les matrices creuses est de l’ordre de O(n2), alors que celle des matrices structurées est en O(n), à des facteurs logarithmiques près.

ALGÈBRE LINÉAIRE DENSE : DE GAUSS À STRASSEN

L’algorithmique des matrices denses constitue l’objet d’étude de ce chapitre. Les matrices creuses seront abordées brièvement au Chapitre 10 et les matrices structurées feront l’objet d’une étude plus approfondie au Chapitre 11.
Nous allons travailler avec un corps eﬀectif noté K et avec l’algèbre des matrices carrées Mn(K) à coeﬃcients dans K. Signalons toutefois que la plupart des résultats de ce chapitre s’étendent au cas où le corps K est remplacé par un anneau eﬀectif A, et les matrices carrées par des matrices rectangulaires à coeﬃcients dans A.
1.2. Résultat principal. Les questions qui seront étudiées, ou simplement évoquées, dans ce chapitre sont celles de la complexité du calcul du produit matri-ciel dans Mn(K), de l’inverse et du déterminant, du polynôme caractéristique ou minimal, de la résolution de systèmes linéaires, ou encore de la mise sous diverses « formes canoniques » (échelon, LUP, compagnon par blocs, . . . )
Pour ces questions, on dispose d’une première famille d’algorithmes « naïfs », reposant sur l’application directe des définitions ou des propriétés mathématiques. Si l’algorithme naïf de multiplication a une complexité raisonnable, cubique en la taille, dans d’autres cas l’emploi des algorithmes naïfs est vivement déconseillé.
Par exemple, si A = (ai;j)ni;j=1 est une matrice de Mn(K), on n’utilisera pas la définition
n
Y
det(A) = sgn( ) ai; (i)
2Sn i=1
pour le calcul de son déterminant ; en eﬀet, cela mènerait à un algorithme de com-plexité O(n n!), donc hyper-exponentielle en la taille de A. De même, la définition du rang d’une matrice comme la taille maximale d’un mineur non-nul ne se prête pas directement, via une recherche exhaustive, à une algorithmisation eﬃcace. Dans un registre légèrement diﬀérent, les formules de Cramer pour résoudre un système linéaire ne sont pas d’une grande utilité pratique (en revanche, elles servent à borner les tailles des solutions, et s’avèrent utiles dans les estimations de complexité).
Une seconde classe d’algorithmes, basés sur la méthode d’élimination de Gauss, permet de résoudre de manière raisonnablement eﬃcace la plupart des problèmes évoqués plus haut. Appliquée à une matrice A de Mn(K), cette méthode fournit des algorithmes de complexité O(n3) pour le calcul de rg(A), de det(A), de A 1 (si A est inversible), celui d’une forme échelonnée et d’une décomposition LUP de A, ainsi que pour la résolution d’un système linéaire de matrice A.
Le résultat principal de ce chapitre est que l’on peut faire mieux, et qu’il existe une constante 2 ! < 3 (dépendante a priori du corps de base K), qui contrôle la complexité du produit matriciel et de toutes les opérations d’algèbre linéaire.
Pour formaliser ce point, on associe à chacun des problèmes son exposant. Dans le cas du produit, il est défini comme suit.
Definition 1 (Exposant de la multiplication matricielle). On dit que le réel est un exposant faisable pour la multiplication de matrices sur le corps K s’il existe un algorithme de complexité arithmétique O(n ) pour multiplier deux matrices arbitraires de Mn(K). On définit !mul = inff j est un exposant faisableg:
A priori, on devrait mettre en indice le corps K pour les exposants et !mul. Les résultats présentés dans la suite sont cependant indépendants de K 1. L’algorithme naïf pour le produit est de complexité O(n3), donc = 3 est un exposant faisable et !mul 3. D’un autre côté, !mul est forcément au moins égal à 2 : le nombre d’éléments d’une matrice est n2 et il faut bien autant d’opérations pour l’écrire.
On peut montrer que la constante !mul ne dépend que de la caractéristique du corps de base K et il est conjecturé qu’elle est même entièrement indépendante du corps K.

MULTIPLICATION DE MATRICES

Ensuite, on peut définir de la même manière les exposants de tous les autres problèmes, de la forme !inv, !polcar, !det, !LUP, etc . . . On a alors le résultat suivant.
Théorème 1. Les exposants !mul, !inv, !polcar, !det, !LUP, sont tous égaux, et inférieurs à 2;38 ; on note ! leur valeur commune. L’exposant correspondant à la résolution de systèmes linéaires est inférieur ou égal à !.
Ce théorème contient deux (familles de) résultats :
– des preuves d’équivalence entre problèmes,
– des bornes supérieures sur leur complexité, c’est-à-dire des algorithmes.
Dans le présent chapitre, il est impossible de démontrer ce théorème dans son intégralité. Nous nous contenterons de prouver (et encore, sous des hypothèses simplificatrices) que le produit et l’inverse ont le même exposant, et que celui-ci est inférieur à log2(7) < 2;81.
Nous montrerons également que !det !polcar !mul = !inv et laisserons en exercice (Exercice 11) la preuve de l’inégalité !inv !det qui permet de conclure que cette suite d’inégalités est en fait une suite d’égalités.
1.3. Applications. Les problèmes d’algèbre linéaire mentionnés ci-dessus sont très fréquemment rencontrés en pratique ; les résultats du Théorème 1 seront in-voqués à plusieurs reprises dans ce cours. Par exemple, l’algorithme de Beckermann-Labahn (Chapitre 9) pour le calcul d’approximants de Padé-Hermite repose ultime-ment sur des produits de matrices de polynômes. C’est aussi le cas de l’algorithme de Storjohann pour la résolution de systèmes linéaires à coeﬃcients polynomiaux (Chapitre 14), et de l’algorithme de recherche de solutions séries d’équations algé-briques (Chapitre 4) ou diﬀérentielles linéaires (Chapitre 15).
De nombreux algorithmes de résolution de systèmes polynomiaux reposent aussi sur de l’algèbre linéaire : les méthodes de calcul d’une base de Gröbner (Chapitre 16) peuvent se ramener à des systèmes linéaires (éventuellement creux) en très grande taille ; l’algorithme de « résolution géométrique » (Chapitre 22) utilise une itération de Newton faisant intervenir des calculs d’inverses de matrices de séries formelles. Dans un contexte diﬀérent, les algorithmes pour les séries D-finies (Chapitre 8) et les algorithmes de sommation et d’intégration (Chapitre 28) font intervenir comme sous-problème la résolution d’un système linéaire.
De façon similaire, la technique du « scindage binaire » qui sera utilisée au Chapitre 13 pour le calcul d’un terme d’une récurrence, ou encore pour le calcul du développement décimal de e, requiert de multiplier des matrices contenant de gros nombres entiers.
L’algèbre linéaire est au cœur de nombreux autres problèmes algorithmiques qui ne seront pas abordés dans ce cours ; c’est le cas de la factorisation des entiers et des polynômes, ou encore du logarithme discret en cryptanalyse. Mentionnons enfin qu’une large partie des ordinateurs du monde passent leurs cycles à faire des calculs d’algèbre linéaire, que ce soit pour faire des calculs d’optimisation combi-natoire (programmation linéaire par l’algorithme du simplexe), de la simulation numérique (méthode des éléments finis), ou de la recherche de pages web (le sys-tème de classement PageRank utilisé par le moteur de recherche Google repose sur la recherche d’un vecteur propre d’une gigantesque matrice creuse).

Multiplication de matrices

Tout comme le produit d’entiers et de polynômes, la multiplication matricielle est une opération fondamentale en calcul formel, dont l’étude de complexité s’avère être un problème hautement non trivial.

ALGÈBRE LINÉAIRE DENSE : DE GAUSS À STRASSEN

L’algorithme naïf pour eﬀectuer le produit d’une matrice de taille m n par un vecteur utilise O(mn) opérations arithmétiques : mn multiplications et m(n 1) additions. Un résultat de Winograd aﬃrme qu’en général on ne peut pas faire mieux : par exemple, pour les matrices réelles dont les coeﬃcients sont algébrique-ment indépendants sur Q, l’algorithme naïf est optimal. Puisque le produit matriciel peut s’interpréter comme une succession de produits matrice-vecteur, une question naturelle est de savoir si la multiplication naïve de deux matrices est aussi quasi-optimale.
La réponse à cette question, et les résultats les plus importants de cette section, classés par ordre chronologique de découverte, sont regroupés dans le théorème suivant.
Théorème 2 (La multiplication naïve n’est pas optimale). Soit K un corps commutatif. On peut multiplier deux matrices de Mn(K) en
O(n3) opérations dans K, par l’algorithme naïf ;
n2dn2 e + 2nbn2 c ’ 12 n3 + n2 multiplications dans K ;
(c) n2dn2 e + (2n 1)bn2 c ’ 12 n3 + n2 n2 multiplications dans K si la caracté-ristique de K est diﬀérente de 2 et si la division par 2 est gratuite ;
O(nlog2(7)) ’ O(n2;81) opérations dans K.
Ces résultats restent valables sur un anneau commutatif A ; pour (a) et (d)
l’hypothèse de commutativité peut même être supprimée. La partie (b) est due
Winograd et fut historiquement la première amélioration de l’algorithme naïf. Elle réduit de moitié le nombre de multiplications, en augmentant en revanche le nombre d’additions. Cela constitue déjà un progrès pour une large classe d’anneaux A dans lesquels la multiplication est plus coûteuse que l’addition 2. Par exemple, la technique du « scindage binaire » qui sera utilisée au Chapitre 13 pour le calcul d’un terme d’une récurrence, ou encore pour le calcul du développement décimal de e, requiert de multiplier des matrices contenant de gros nombres entiers.
L’amélioration (c) a été obtenue par Waksman, et implique qu’on peut eﬀectuer le produit de deux matrices 2 2 en 7 multiplications. L’inconvénient commun des algorithmes de Winograd et de Waksman est l’utilisation de la commutativité de K, qui devient un obstacle à une application récursive, ne permettant pas d’améliorer (la borne supérieure 3 sur) l’exposant !mul. Beaucoup pensaient que tout résultat de type (b) et (c) serait optimal, au sens que 12 n3 multiplications dans K seraient nécessaires pour le produit dans Mn(K). Ceci fut contredit par la découverte par Strassen de (d) ; ce résultat découle d’un fait d’une simplicité déconcertante, mais d’une portée considérable : deux matrices 2 2 peuvent être multipliées en 7 mul-tiplications même si K n’est pas commutatif.
La non-optimalité de la multiplication matricielle naïve justifie l’introduction de la définition suivante.
Definition 2 (Fonction de multiplication matricielle). On dit que l’application : N ! N est une fonction de multiplication matricielle (pour un corps K) si : on peut multiplier des matrices de Mn(K) en au plus MM(n) opérations dans K ;
MM est croissante et vérifie l’inégalité MM(n=2) MM(n)=4 pour n 2 N.
Ainsi, le Théorème 2 montre que les fonctions n 7!n3 ou n 7!nlog2(7) sont (à des constantes près) des fonctions de multiplication matricielles. Comme dans le cas de la fonction de multiplication polynomiale M introduite au Chapitre 2,
C’est par exemple le cas de Z et de Z[X], mais pas de Q ou de Q(X).

MULTIPLICATION DE MATRICES

l’intérêt de cette notion est qu’elle permet d’énoncer des résultats de complexité indépendants du choix de l’algorithme utilisé pour multiplier les matrices.
La seconde condition de la Définition 2 établit la cohérence avec la Définition 1 : si MM(n) = c n , pour une certaine constante c > 0, alors doit être supérieur ou égal à 2. Cette condition permettra de montrer que dans des algorithmes de type diviser pour régner » pour les matrices, le coût total est essentiellement celui du dernier appel récursif.
Le reste de cette section est dédié à la preuve du Théorème 2.
2.1. Multiplication naïve. Commençons par décrire l’algorithme « cu-bique » de multiplication. Étant données deux matrices A = (ai;j)ni;j=1 et X = (xi;j)ni;j=1 de Mn(K), leur produit s’écrit R = AX avec
n
X
ri;k = ai;jxj;k:
j=1
Le coût nécessaire pour obtenir un élément de R est donc de n multiplications et 1 additions, de sorte que la complexité totale est en O(n3).

Introduction
Chapitre 1. Calcul Formel et Complexité
1. Décider, calculer
2. Calculer rapidement
Première partie. Algorithmes Fondamentaux
Chapitre 2. Multiplication rapide
1. Introduction, résultats principaux
2. Algorithme naïf
3. Algorithme de Karatsuba
4. Transformée de Fourier rapide
5. L’algorithme de Schönhage et Strassen
6. Algorithmes pour les entiers
7. Un concept important : les fonctions de multiplication
Chapitre 3. Algèbre linéaire dense : de Gauss à Strassen
1. Introduction
2. Multiplication de matrices
3. Autres problèmes d’algèbre linéaire
Chapitre 4. Calculs rapides sur les séries
1. Séries formelles
2. La méthode de Newton pour le calcul d’inverses
3. Itération de Newton formelle et applications
4. La composition des séries
Chapitre 5. Division euclidienne, fractions rationnelles et récurrences linéaires à coefficients constants
1. Introduction
2. Division de polynômes
3. Suites récurrentes linéaires à coefficients constants
4. Développement de fractions rationnelles
5. Applications
Chapitre 6. Calculs modulaires, évaluation et interpolation
1. Introduction
2. Présentation, résultats
3. Interpolation de Lagrange
4. Algorithmes rapides
Chapitre 7. Pgcd et résultant
1. Algorithme d’Euclide
2. Résultant
3. Algorithme d’Euclide rapide
Chapitre 8. Algorithmique des séries D-finies
1. Équations différentielles et récurrences
2. Propriétés de clôture
3. Séries algébriques
4. ? Au-delà ?
Chapitre 9. Approximants de Padé et de Padé-Hermite
1. Reconstruction rationnelle
2. Approximants de Padé-Hermite
Chapitre 10. Algèbre linéaire creuse : algorithme de Wiedemann
1. Introduction
2. Polynôme minimal et résolution de systèmes
3. Calcul du polynôme minimal
4. Calcul du déterminant
5. Calcul du rang
Chapitre 11. Algèbre linéaire structurée
1. Introduction
2. Le cas quasi-Toeplitz
Chapitre 12. Principe de transposition de Tellegen
1. Introduction
2. La version en termes de graphes du principe de Tellegen
3. Principe de Tellegen pour les programmes linéaires
4. Applications
Chapitre 13. Récurrences linéaires à coefficients polynomiaux : N-ième terme, N premiers termes
1. Calcul naïf de N! et de suites P-récursives
2. Pas de bébés et pas de géants
3. Scindage binaire
Chapitre 14. Solutions rationnelles de systèmes linéaires à coefficients polynomiaux
1. Des séries aux solutions rationnelles
2. Développement comme une fraction rationnelle
3. L’algorithme de Storjohann
Chapitre 15. Solutions séries d’équations différentielles
1. Équations différentielles d’ordre 1
2. Équations différentielles linéaires d’ordre supérieur et systèmes d’ordre 1
3. Cas particuliers
4. Extensions
Deuxième partie. Systèmes Polynomiaux
Chapitre 16. Bases standard
1. Lien entre algèbre et géométrie
2. Ordres totaux admissibles sur le monoïde des monômes
3. Exposants privilégiés et escaliers
4. Noethérianité du monoïde des monômes
5. Divisions
Chapitre 17. Module de syzygies et construction de bases standard
1. Algorithme naïf par algèbre linéaire
2. Polynôme de syzygie
3. L’algorithme de construction de Buchberger
4. L’algorithme de construction en affine
5. Exemple de calcul
6. Propriétés des bases standards pour quelques ordres
Chapitre 18. Triangularisation des idéaux, Nullstellensatz
1. Le lemme de spécialisation
2. Triangulation des idéaux
3. Le Nullstellensatz
Chapitre 19. Fonction et polynôme de Hilbert, dimension, degré
1. Définitions
2. Démonstration du théorème et d’une borne supérieure de la régularité
3. Optimalité de la borne sur le degré de régularité
4. Le cas des suites régulières
5. Théorie de la dimension
6. Remarque sur la calculabilité de la dimension
Chapitre 20. Le lemme de normalisation de Noether
1. La situation linéaire
2. La situation générale
Chapitre 21. Quête d’une meilleure complexité
1. Test à zéro, ensembles questeurs
2. Structures de données pour les polynômes multivariés
3. Quelques algorithmes utilisant des SLP
Chapitre 22. Résolution géométrique
Troisième partie. Sommation et intégration de suites et fonctions spéciales
Chapitre 23. Résolution d’équations différentielles linéaires
1. Système et équation
2. Solutions séries et singularités
3. Solutions polynomiales
4. Solutions rationnelle
Chapitre 24. Solutions rationnelles de récurrences et sommation hypergéométrique indéfinie
1. Solutions polynomiales
2. Solutions rationnelles : Algorithme d’Abramov
3. Équations inhomogènes
4. Sommation hypergéométrique indéfinie. Algorithme de Gosper
Chapitre 25. Solutions hypergéométriques de récurrences et sommation hypergéométrique définie
1. Sommation hypergéométrique définie. Algorithme de Zeilberger
2. Solutions hypergéométriques. Algorithme de Petkovšek
Chapitre 26. Équations fonctionnelles linéaires et polynômes tordus
1. Des polynômes non commutatifs pour calculer avec des opérateurs linéaires
2. Clôtures par morphismes entre anneaux de polynômes tordus
3. Division euclidienne
4. Recherche de solutions et factorisation d’opérateurs
5. Algorithme d’Euclide
6. Relations de contiguïté
Chapitre 27. Algorithmes pour les fonctions spéciales dans les algèbres de Ore
1. Algèbres de Ore rationnelles
2. Idéal annulateur et module quotient
3. Bases de Gröbner pour les idéaux à gauche
4. ? Module quotient et dimension de l’espace des solutions ?
5. Les fonctions @-finies et leurs clôtures
Chapitre 28. Sommation et intégration symboliques des fonctions spéciales
1. Expression du télescopage créatif en termes d’algèbres de Ore rationnelles
2. L’algorithme sur l’exemple 1 2J0(x)2 + J1(x)2 + J2(x)2 + = 12
3. Bases de Gröbner de modules et découplage de systèmes
Quatrième partie. Compléments
Chapitre 29. Réduction de réseaux et algorithme LLL
1. Réseaux, vecteurs courts et résultats principaux
2. Applications
3. Le procédé d’orthogonalisation de Gram–Schmidt
4. L’algorithme LLL
5. Preuve de l’algorithme LLL
Chapitre 30. Factorisation des polynômes
1. Introduction
2. Corps finis, quelques rappels
3. Partie sans carré et décomposition sans carré
4. Algorithme de Berlekamp
Chapitre 31. Exercices récapitulatifs
Bibliographie