MÉTHODES MATRICIELLES
INTRODUCTION À LA COMPLEXITÉ ALGÉBRIQUE
Avant-Propos
1 Rappels d'Algèbre linéaire
1.1 Quelques propriétés générales
1.1.1 Notations
1.1.2 Formule de Binet-Cauchy
1.1.3 Rang, déterminant et identités de Cramer
1.1.4 Identités de Sylvester
1.2 Polynôme caractéristique
1.2.1 Matrice caractéristique adjointe
1.2.2 Formule de Samuelson
1.2.3 Valeurs propres de f(A)
1.3 Polynôme minimal
1.3.1 Sous-espaces de Krylov
1.3.2 Cas de matrices à coefficients dans Z
1.4 Suites récurrentes linéaires
1.4.1 Polynôme générateur, opérateur de décalage
1.4.2 Matrices de Hankel
1.5 Polynômes symétriques et relations de Newton
1.6 Inégalité de Hadamard et calcul modulaire
1.6.1 Normes matricielles
1.6.2 Théorème chinois et applications
1.7 Résolution uniforme des systèmes linéaires
1.7.1 L'inverse de Moore-Penrose
1.7.2 Généralisation sur un corps arbitraire
2 Algorithmes de base en algèbre linéaire
2.1 Méthode du pivot de Gauss
2.1.1 Transformations élémentaires
2.1.2 La LU-décomposition
2.1.3 Recherche de pivot non nul
2.2 Méthode de Jordan-Bareiss
2.2.1 Formule de Dodgson-Jordan-Bareiss
2.2.2 Méthode de Jordan-Bareiss modifiée
2.2.3 La méthode de Dodgson
2.3 Méthode de Hessenberg
2.4 Méthode d'interpolation de Lagrange
2.5 Méthode de Le Verrier et variantes
2.5.1 Le principe général
2.5.2 Méthode de Souriau-Faddeev-Frame
2.5.3 Méthode de Preparata & Sarwate
2.6 Méthode de Samuelson-Berkowitz
2.6.1 Principe général de l'algorithme
2.6.2 Version séquentielle
2.7 Méthode de Chistov
2.7.1 Le principe général
2.7.2 La version séquentielle
2.8 Méthodes reliées aux suites récurrentes linéaires
2.8.1 L'algorithme de Frobenius
2.8.2 Algorithme de Berlekamp/Massey
2.8.3 Méthode de Wiedemann
3 Circuits arithmétiques
3.1 Circuits arithmétiques et programmes d'évaluation
3.1.1 Quelques définitions
3.1.2 Circuit arithmétique vu comme un graphe
3.1.3 Circuits arithmétiques homogènes
3.1.4 Le problème des divisions
3.2 Élimination des divisions à la Strassen
3.2.1 Le principe général
3.2.2 Coût de l'élimination des divisions
3.3 Calcul des dérivées partielles
4 Notions de complexité
4.1 Machines de Turing et Machines à Accès Direct
4.2 Complexité binaire, les classes P, NP et #P
4.2.1 Calculs faisables
4.2.2 Quand les solutions sont faciles à tester
4.2.3 Problèmes de comptage
4.3 Complexités arithmétique et binaire
4.3.1 Complexité arithmétique
4.3.2 Complexité binaire
4.4 Familles uniformes de circuits
4.5 Machines parallèles à accès direct
4.5.1 Une idéalisation des calculs parallèles sur ordinateur
4.5.2 PRAM-complexité et Processeur-efficacité
4.5.3 Le principe de Brent
5 Diviser pour gagner
5.1 Le principe général
5.2 Circuit binaire équilibré
5.3 Calcul parallèle des préfixes
6 Multiplication rapide des polynômes
6.1 Méthode de Karatsuba
6.2 Transformation de Fourier discrète usuelle
6.3 Transformation de Fourier discrète rapide
6.3.1 Cas favorable
6.3.2 Cas d'un anneau commutatif arbitraire
6.4 Produits de matrices de Toeplitz
7 Multiplication rapide des matrices
7.1 Analyse de la méthode de Strassen
7.1.1 La méthode et sa complexité
7.1.2 Une famille uniforme de circuits arithmétiques
7.2 Inversion des matrices triangulaires
7.3 Complexité bilinéaire
7.3.1 Rang tensoriel d'une application bilinéaire
7.3.2 Exposant de la multiplication des matrices carrées
7.3.3 Complexité bilinéaire versus complexité multiplicative
7.3.4 Extension du corps de base
7.4 Calculs bilinéaires approximatifs
7.4.1 Méthode de Bini
7.4.2 Une amélioration décisive de Schönhage
7.4.3 Sommes directes d'applications bilinéaires
7.4.4 L'inégalité asymptotique de Schönhage
8 Algèbre linéaire séquentielle rapide
8.1 L'Algorithme de Bunch & Hopcroft
8.2 Calcul du déterminant et de l'inverse
8.3 Forme réduite échelonnée en lignes
8.4 Méthode de Keller-Gehrig
8.5 Méthode de Kaltofen-Wiedemann
9 Parallélisations de la méthode de Leverrier
9.1 Algorithme de Csanky
9.2 Amélioration de Preparata et Sarwate
9.3 Amélioration de Galil et Pan
10 Polynôme caractéristique sur un anneau arbitraire
10.1 Méthode générale de parallélisation
10.2 Algorithme de Berkowitz amélioré
10.3 Méthode de Chistov
10.4 Applications des algorithmes
11 Résultats expérimentaux
11.1 Tableaux récapitulatifs des complexités
11.2 Présentation des tests
11.3 Tableaux de Comparaison
12 Le déterminant et les expressions arithmétiques
12.1 Expressions, circuits et descriptions
12.2 Parallélisation des expressions et des circuits
12.3 La plupart des polynômes sont difficiles à évaluer
12.4 Le caractère universel du déterminant
13 Le permanent et la conjecture ¬(P = NP)
13.1 Familles d'expressions et de circuits booléens
13.2 Booléen versus algébrique
13.2.1 Évaluation booléenne des circuits arithmétiques
13.2.2 Simulation algébrique des circuits et expressions booléennes
13.2.3 Formes algébriques déployées
13.3 Complexité binaire versus complexité booléenne
13.4 Le caractère universel du permanent
13.5 La conjecture de Valiant
Annexe : codes Maple Tables, bibliographie, index