Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Journées Nationales de Calcul Formel Rencontre organisée par : Jean-Guillaume D

Journées Nationales de Calcul Formel Rencontre organisée par : Jean-Guillaume Dumas, Grégoire Lecerf, Delphine Boucher et Thomas Cluzeau 2010 Alin Bostan Algorithmes rapides pour les polynômes, séries formelles et matrices Vol. 1, no 2 (2010), p. 75-262. <http://ccirm.cedram.org/item?id=CCIRM_2010__1_2_75_0> Centre international de rencontres mathématiques U.M.S. 822 C.N.R.S./S.M.F. Luminy (Marseille) France cedram Texte mis en ligne dans le cadre du Centre de diffusion des revues académiques de mathématiques http://www.cedram.org/ Les cours du C.I.R.M. Vol. 1 no 2 (2010) 75-262 Algorithmes rapides pour les polynômes, séries formelles et matrices Alin Bostan Table des matières Avant-propos 81 Chapitre 1. Calcul Formel et Complexité 83 1. Décider, calculer 83 1.1. Fondements logiques 83 1.2. Structures et constructions de base 83 1.3. Équations comme structures de données 85 2. Calculer rapidement 86 2.1. Mesures de complexité 87 2.2. La notation O(·) 88 2.3. Diviser pour régner 88 Avertissement 90 Notes 91 Bibliographie 91 Chapitre 2. Multiplication rapide 93 1. Introduction, résultats principaux 93 2. Algorithme naïf 95 3. Algorithme de Karatsuba 96 4. Transformée de Fourier rapide 97 4.1. Idée de l’algorithme 97 4.2. Racines primitives de l’unité 97 4.3. Transformée de Fourier rapide 98 4.4. Interpolation 99 4.5. Conclusion 100 4.6. Mais où sont nos racines ? 100 5. L’algorithme de Schönhage et Strassen 101 5.1. Racines virtuelles de l’unité 101 5.2. L’algorithme 101 6. Algorithmes pour les entiers 102 7. Un concept important : les fonctions de multiplication 103 Exercices 103 Notes 104 Bibliographie 105 Chapitre 3. Algèbre linéaire dense : de Gauss à Strassen 107 1. Introduction 107 1.1. L’algorithmique des matrices : tentative de classiﬁcation 107 Cours professé lors de la rencontre « Journées Nationales de Calcul Formel » organisée par Jean-Guillaume Dumas, Grégoire Lecerf, Delphine Boucher et Thomas Cluzeau. 3-7 mai 2010, C.I.R.M. (Luminy). 75 Alin Bostan 1.2. Résultat principal 108 1.3. Applications. 109 2. Multiplication de matrices 109 2.1. Multiplication naïve 110 2.2. Algorithme de Winograd 110 2.3. Algorithme de Waksman 110 2.4. Algorithme de Strassen 111 2.5. Interprétation des formules de Strassen 113 2.6. Peut-on faire mieux que 2,81 ? 114 2.7. En pratique 114 3. Autres problèmes d’algèbre linéaire 115 3.1. Élimination de Gauss 115 3.2. Résultat principal 116 3.3. La multiplication n’est pas plus diﬃcile que l’inversion. 116 3.4. L’inversion, le calcul de déterminant et la résolution de système ne sont pas plus diﬃciles que la multiplication. 116 3.5. Calcul du polynôme caractéristique 118 Exercices 119 Notes 121 Bibliographie 124 Chapitre 4. Calculs rapides sur les séries 127 1. Séries formelles 128 2. La méthode de Newton pour le calcul d’inverses 130 2.1. Convergence quadratique pour l’inverse d’une série formelle 130 2.2. Algorithme 130 2.3. Complexité 130 2.4. Division de séries 131 2.5. Application à la division Euclidienne 131 2.6. Application au logarithme 131 2.7. Extension : inverse de matrices 131 3. Itération de Newton formelle et applications 132 3.1. Un résultat général 132 3.2. Algorithme 132 3.3. Applications 133 3.4. Exponentielle 133 3.5. Sommes de Newton 133 3.6. Application à la somme et au produit composés 134 3.7. Inverse compositionnel 135 3.8. Systèmes 136 4. La composition des séries 136 4.1. Méthode naïve 136 4.2. Pas de bébés—pas de géants 136 4.3. L’algorithme de Brent & Kung 137 Exercices 138 Notes 139 Bibliographie 139 Chapitre 5. Division euclidienne, fractions rationnelles et récurrences linéaires à coeﬃcients constants 141 1. Division de polynômes 141 1.1. Méthode naïve 141 1.2. Algorithme rapide 141 1.3. Le cas des entiers 142 1.4. Application aux calculs modulaires 142 2. Développement de fractions rationnelles 143 76 Algorithmes rapides pour les polynômes, séries formelles et matrices 3. Suites récurrentes linéaires à coeﬃcients constants 144 3.1. Prélude : les nombres de Fibonacci 144 3.2. Calcul rapide des termes d’une suite 144 3.3. Propriétés de clôture 145 3.4. Application : tests de primalité 146 Notes 146 Bibliographie 147 Chapitre 6. Calculs modulaires, évaluation et interpolation 149 1. Introduction 149 2. Présentation, résultats 150 3. Interpolation de Lagrange 151 4. Algorithmes rapides 152 4.1. Les idées 152 4.2. L’arbre des sous-produits 152 4.3. Évaluation multipoint rapide 153 4.4. Sommes de fractions 154 4.5. Interpolation 155 4.6. Évaluation et interpolation sur une suite géométrique. 156 Exercices 157 Notes 157 Bibliographie 158 Chapitre 7. Pgcd et résultant 159 1. Algorithme d’Euclide 159 1.1. Le pgcd 159 1.2. Calcul du pgcd 160 1.3. Pgcd étendu et inversion modulaire 161 2. Résultant 162 2.1. Matrice de Sylvester 162 2.2. Applications du résultant 164 2.3. Propriétés et calcul quadratique 166 2.4. Calcul avec des nombres algébriques 167 2.5. Sous-résultants 167 3. Algorithme d’Euclide rapide 170 3.1. Demi-pgcd : déﬁnition. 170 3.2. Demi-pgcd : algorithme. 171 3.3. Complément : calcul d’un reste choisi. 172 3.4. Le cas des entiers. 173 Exercices 173 Notes 173 Bibliographie 174 Chapitre 8. Algorithmique des séries D-ﬁnies 177 1. Équations diﬀérentielles et récurrences 177 1.1. Déﬁnitions 177 1.2. Méthode naïve 177 1.3. Exemples d’applications 178 1.4. Algorithme rapide 179 2. Propriétés de clôture 180 2.1. Somme et produit 180 2.2. Produit d’Hadamard 181 3. Séries algébriques 181 4. Limitations 182 Exercices 183 Notes 184 77 Alin Bostan Bibliographie 184 Chapitre 9. Approximants de Padé et de Padé-Hermite 187 1. Reconstruction rationnelle 187 1.1. Calcul de la reconstruction rationnelle 188 1.2. Approximants de Padé 189 1.3. Algorithme de Berlekamp-Massey 190 1.4. Interpolation rationnelle de Cauchy 190 1.5. Algorithmes rapides 191 2. Approximants de Padé-Hermite 191 2.1. Algorithme de Derksen : idées et résultats préliminaires 192 2.2. Algorithme de Derksen : fonctionnement 193 2.3. Approximants de Padé-Hermite de type arbitraire 194 2.4. Applications 194 2.5. Calcul quasi-optimal 196 Notes 196 Bibliographie 197 Chapitre 10. Algèbre linéaire creuse : algorithme de Wiedemann 199 1. Introduction 199 2. Polynôme minimal et résolution de systèmes 199 3. Calcul du polynôme minimal 200 4. Calcul du déterminant 201 5. Calcul du rang 201 Exercices 201 Notes 202 Bibliographie 202 Chapitre 11. Algèbre linéaire structurée 203 1. Introduction 203 2. Le cas quasi-Toeplitz 206 2.1. Produit matrice-vecteur, cas quasi-Toeplitz 207 2.2. Addition et produit en représentation compacte par générateurs 207 2.3. Inversion en représentation compacte par générateurs 208 2.4. Résolution rapide de systèmes quasi-Toeplitz 209 Exercices 209 Notes 210 Bibliographie 210 Chapitre 12. Principe de transposition de Tellegen 213 1. Introduction 213 2. La version en termes de graphes du principe de Tellegen 214 3. Principe de Tellegen pour les programmes linéaires 216 3.1. Machines à registres 216 3.2. Transposition de programme 216 3.3. Optimisations 217 4. Applications 217 4.1. Produit médian des polynômes 218 4.2. Division avec reste et extension des récurrences à coeﬃcients constants 219 4.3. Évaluation multipoint et interpolation 220 4.4. Bonus : l’évaluation et l’interpolation ont des coûts équivalents 221 Notes 222 Bibliographie 224 Chapitre 13. Récurrences linéaires à coeﬃcients polynomiaux : N-ième terme, N premiers termes 227 1. Calcul naïf de N! et de suites P-récursives 227 78 Algorithmes rapides pour les polynômes, séries formelles et matrices 1.1. Cas de la factorielle 227 1.2. Cas général 228 2. Pas de bébés et pas de géants 229 2.1. Factorisation déterministe des entiers. 229 3. Scindage binaire 230 3.1. Cas de la factorielle 230 3.2. Récurrences d’ordre 1 230 3.3. Calcul de e = exp(1) 231 3.4. Suites polynomialement récursives 231 Exercices 231 Notes 232 Bibliographie 232 Chapitre 14. Solutions rationnelles de systèmes linéaires à coeﬃcients polynomiaux 235 1. Des séries aux solutions rationnelles 235 2. Développement comme une fraction rationnelle 236 3. L’algorithme de Storjohann 237 Notes 238 Bibliographie 238 Chapitre 15. Solutions séries d’équations diﬀérentielles 241 1. Équations diﬀérentielles d’ordre 1 241 1.1. L’équation linéaire homogène du premier ordre 241 1.2. L’équation linéaire inhomogène du premier ordre 242 1.3. Le cas non-linéaire 242 2. Équations diﬀérentielles linéaires d’ordre supérieur et systèmes d’ordre 1 243 2.1. Une méthode par « diviser pour régner » 243 2.2. L’itération de Newton matricielle 244 3. Cas particuliers 246 3.1. Équations diﬀérentielles linéaires à coeﬃcients polynomiaux 246 3.2. Équations diﬀérentielles linéaires à coeﬃcients constants 246 4. Extensions 247 4.1. Composer se ramène à résoudre 247 4.2. Systèmes non-linéaires 248 Notes 248 Bibliographie 248 Chapitre 16. Exercices récapitulatifs 249 Notes 259 Bibliographie 259 Annexe : liste des algorithmes 261 79 Algorithmes rapides pour les polynômes, séries formelles et matrices Avant-propos Le calcul formel calcule des objets mathématiques exacts. Ce cours explore deux directions : la calculabilité et la complexité. La calculabilité étudie les classes d’objets mathématiques sur lesquelles des réponses peuvent être obtenues algorithmiquement. La complexité donne ensuite des outils pour comparer des algorithmes du point de vue de leur eﬃcacité. Ce cours passe en revue l’algorithmique eﬃcace sur les objets fondamentaux que sont les entiers, les polynômes, les matrices, les séries et les solutions d’équations diﬀérentielles ou de récurrences linéaires. On y montre que de nombreuses questions portant sur ces objets admettent une réponse en complexité (quasi-)optimale, en insistant sur les principes généraux de conception d’algorithmes eﬃcaces. Ces notes sont dérivées du cours « Algorithmes eﬃcaces en calcul formel » du Master Parisien de Recherche en Informatique (2004–2010), co-écrit avec Frédéric Chyzak, Marc Giusti, Romain Lebreton, Bruno Salvy et Éric Schost. Le support de cours uploads/s3/ bostan10-algorithmes-rapides.pdf