Algorithmes Efficaces en Calcul Formel

Description

Le calcul formel calcule des objets mathématiques exacts.

Informations

• Publié par: Force_IT
• Nombre de lectures: 21
• Licence : En savoir +
  Paternité, pas d'utilisation commerciale, partage des conditions initiales à l'identique
• Langue: Français
• Poids de l'ouvrage: 2 Mo

Extrait

Algorithmes Efficaces en Calcul Formel
Notes du cours 2-22 du MPRI
Version du 11 février 2014

Alin Bostan
Frédéric Chyzak
Marc Giusti
Romain Lebreton
Grégoire Lecerf
Bruno Salvy
Éric Schost

Table des matières

Les chapitres ou sections indiqués par?peuvent tre omis en première lecture.
Ils ne sont généralement pas traités dans le cours oral.
Introduction1
Chapitre 1. Calcul formel et complexité3
1. Décider,calculer3
2. Calculerrapidement8
Conventions14
Notes14
Bibliographie15

Première partie.Polynômes et séries17
Chapitre 2. Multiplication rapide19
1. Introduction,résultats principaux19
2. Algorithmenaïf21
3. Algorithmede Karatsuba22
4. Transforméede Fourier rapide24
5. L’algorithmede Schönhage et Strassen28
6. Algorithmespour les entiers29
7. Unconcept important : les fonctions de multiplication30
Exercices31
Notes32
Bibliographie33
Chapitre 3. Calculs rapides sur les séries37
1. Sériesformelles38
2. Laméthode de Newton pour le calcul d’inverses40
3. Itérationde Newton formelle et applications42
4. Lacomposition des séries49
Exercices52
Notes52
Bibliographie53
Chapitre 4. Division euclidienne, fractions rationnelles et récurrences linéaires
à coefficients constants57
1. Introduction57
2. Divisionde polynômes57
3. Suitesrécurrentes linéaires à coefficients constants60
4. Développementde fractions rationnelles62
5. Applications64
Notes65
Bibliographie66
iii

iv TABLEDES MATIèRES
Chapitre 5. Calculs modulaires, évaluation et interpolation
1. Introduction
2. Présentation,résultats
3. Interpolationde Lagrange
4. Algorithmesrapides
Exercices
Notes
Bibliographie

Chapitre 6. Pgcd et résultant
1. Algorithmed’Euclide
2. Résultant
3. Algorithmed’Euclide rapide
Exercices
Notes
Bibliographie

Chapitre 7. Approximants de Padé et de Padé-Hermite
1. Reconstructionrationnelle
2. Approximantsde Padé-Hermite
Notes
Bibliographie

Deuxième partie.Matrices

Chapitre 8. Algèbre linéaire dense : de Gauss à Strassen
1. Introduction
2. Multiplicationde matrices
3. Autresproblèmes d’algèbre linéaire
Exercices
Notes
Bibliographie

Chapitre 9. Algèbre linéaire creuse : algorithme de Wiedemann
1. Introduction
2. Polynômeminimal et résolution de systèmes
3. Calculdu polynôme minimal
4. Calculdu déterminant
5. Calculdu rang
Exercices
Notes
Bibliographie

Chapitre 10. Algèbre linéaire structurée
1. Introduction
2. Lecas quasi-Toeplitz
Exercices
Notes
Bibliographie

67
67
68
69
70
75
76
77

79
79
83
91
95
96
97

101
101
106
111
112

115
117
117
119
126
131
134
137
141
141
141
142
143
143
143
144
144
147
147
151
155
155
156

Chapitre 11. Solutions rationnelles de systèmes linéaires à coefficients
polynomiaux159
1. Desséries aux solutions rationnelles159
2. Développementcomme une fraction rationnelle160

TABLE DES MATIèRESv
3. L’algorithmede Storjohann161
Notes162
Bibliographie163
Chapitre 12.?Principe de transposition de Tellegen?165
1. Introduction165
2. Laversion en termes de graphes du principe de Tellegen166
3. Principede Tellegen pour les programmes linéaires168
4. Applications170
Notes175
Bibliographie177
Chapitre 13.?Équations différentielles à coefficients séries?181
1. Équationsdifférentielles d’ordre 1181
2. Équationsdifférentielles linéaires d’ordre supérieur et systèmes d’ordre 1183
3. Casparticuliers187
4. Extensions187
Notes189
Bibliographie189

Troisième partie.Équations différentielles et récurrences linéaires191
Chapitre 14. Algorithmique des séries D-finies193
1. Équationsdifférentielles et récurrences193
2. Propriétésde clôture197
3. Sériesalgébriques199
4.?Au-delà?200
Exercices201
Notes202
Bibliographie203
Chapitre 15. Récurrences linéaires à coefficients polynomiaux :N-ième terme,
Npremiers termes205
1. Calculnaïf deN!et de suites P-récursives206
2. Pasde bébés et pas de géants207
3. Scindagebinaire209
Exercices212
Notes213
Bibliographie213
Chapitre 16. Résolution d’équations différentielles et de récurrences linéaires215
1. Suiteset séries216
2. Solutionsà support fini219
3. Solutionspolynomiales221
4. Solutionsrationnelles224
5. Exercices227
Notes228
Bibliographie229

Quatrième partie.Systèmes Polynomiaux

Chapitre 17. Bases standard
1. Lienentre algèbre et géométrie
2. Ordrestotaux admissibles sur le monoïde des monômes

231
233
234
237

vi TABLEDES MATIèRES
3. Exposantsprivilégiés et escaliers
4. Noethérianitédu monoïde des monômes
5. Divisions
Bibliographie

Chapitre 18. Construction de bases standard
1. Algorithmenaïf par algèbre linéaire
2. Polynômede syzygie
3. L’algorithmede construction de Buchberger
4. Exemplede calcul
5. Propriétésdes bases standard pour quelques ordres
Notes
Bibliographie

Chapitre 19. Nullstellensatz et applications
1. Nullstellensatzaffine
2. Nullstellensatzprojectif
3. Idéauxde dimension zéro
4. Projectiondes variétés affines
5. Projectiondes variétés projectives
Bibliographie

Chapitre 20. Fonction et polynôme de Hilbert, dimension, degré
1. Fonctionet polynôme de Hilbert
2. Démonstrationset borne supérieure de la régularité
3. Suitesrégulières
4. Autresdéfinitions de la dimension
Notes
Bibliographie

Chapitre 21. Normalisation de Noether
1. Lasituation linéaire
2. Lasituation générale
3.?Test à zéro d’un polynôme?
Notes
Bibliographie

Chapitre 22. Résolution géométrique
1. Polynômescaractéristiques et minimaux
2. Élémentprimitif
3. Intersection
4. Remontéede Hensel
5. Résolutiongéométrique
Notes
Bibliographie

239
240
241
243

245
245
246
246
248
249
250
251

253
253
256
256
257
258
260

261
261
262
263
264
265
265

267
267
268
271
273
273

275
275
277
279
283
285
286
286

Cinquième partie.Sommation et intégration de suites et fonctions
spéciales289
Chapitre 23. Solutions hypergéométriques de récurrences et sommation
hypergéométrique291
1. Sommationhypergéométrique indéfinie. Algorithme de Gosper292
2. Sommationhypergéométrique définie. Algorithme de Zeilberger294
3. Solutionshypergéométriques. Algorithme de Petkovek296

TABLE DES MATIèRESvii
Notes298
Bibliographie298
Chapitre 24. Équations fonctionnelles linéaires et polynômes tordus299
1. Despolynômes non commutatifs pour calculer avec des opérateurs
linéaires299
2. Clôturespar morphismes entre anneaux de polynômes tordus301
3. Divisioneuclidienne303
4. Recherchede solutions et factorisation d’opérateurs305
5. Algorithmed’Euclide306
6. Relationsde contiguïté307
Notes309
Bibliographie310
Chapitre 25. Algorithmes pour les fonctions spéciales dans les algèbres de Ore311
1. Algèbresde Ore rationnelles311
2. Idéalannulateur et module quotient311
3. Basesde Gröbner pour les idéaux à gauche313
4.?Module quotient et dimension de l’espace des solutions?314
5. Lesfonctions∂-finies et leurs clôtures318
Notes321
Bibliographie322
Chapitre 26. Sommation et intégration symboliques des fonctions spéciales323
1. Expressiondu télescopage créatif en termes d’algèbres de Ore
rationnelles323
1 22 21
2. L’algorithmesur l’exempleJ0(x) +J1(x) +J2(x) +∙ ∙ ∙=325
2 2
3. Basesde Gröbner de modules et