Parisian Master of Research in Computer Science
Master Parisien de Recherche en Informatique (MPRI)

Algorithmes efficaces en calcul formel (48h, 6 ECTS)

Responsable : B. Salvy

Objectifs

Le calcul formel (computer algebra ou symbolic computation en anglais) consiste à représenter et manipuler sur ordinateur des objets mathématiques de manière exacte, par opposition au calcul scientifique traditionnel. Les contreparties de telles représentations sont souvent des temps de calculs importants et une explosion de la taille mémoire nécessaire lorsque l'on utilise des algorithmes naïfs. Dans ce cours, nous présentons les algorithmes de base du calcul formel sur les polynômes, séries et matrices qui permettent d'atteindre dans de nombreux cas des bornes de complexité quasi-optimales. Ces algorithmes sont très largement utilisés en pratique dans des logiciels de calcul formel mais aussi dans plusieurs autres domaines algorithmiques modernes reposant sur des techniques algébriques, telles que la cryptographie, cryptanalyse multivariée, et les codes correcteurs d'erreurs.

Dans un deuxième temps nous abordons des thèmes actifs de recherche plus spécialisés, comme la sommation et l'intégration symbolique. Les méthodes de sommation et intégration symbolique que nous présentons ont conduit à des outils de calcul désormais incontournables pour la physique, l'évaluation numérique des fonctions spéciales, la modélisation des problèmes combinatoires, et plus largement pour les questions difficiles de simplification de formules.

Ce cours est particulièrement bien adapté pour comprendre avec rigueur les bases algorithmiques et leurs principes généraux en complément des cours Systèmes polynomiaux, calcul formel et applications (2-13-1), Codes correcteurs d'erreurs et applications à la cryptographie (2-13-2), Techniques en cryptographie et cryptanalyse (2-12-1), Algorithmes arithmétiques pour la cryptologie (2-12-2).

Plan du cours et intervenants prévus pour 2018-2019

  • Algorithmes fondamentaux
  • Sommation et intégration de suites et fonctions spéciales

Alin Bostan (27h),Frédéric Chyzak (12h),Bruno Salvy (9h)

Cette page contient le programme de l'ensemble du cours et sera modifiée hebdomadairement pour incorporer les divers supports et éventuellement faire évoluer les sujets des séances en fonction de ce qui aura été présenté en cours.

Langues du cours

Le cours sera en français. Les étudiants sont autorisés à rédiger leurs examens en français ou en anglais.

La note du cours est la moyenne des notes obtenues au partiel et à l'examen final. Les documents autorisés aux examens sont le poly et les notes de cours de l'étudiant.

Cours 1. 13/09

Bruno Salvy.

Présentation générale du cours, multiplication rapide. (Chap. 1 et 2)

Exercices

Cours 2. 20/09

Bruno Salvy.

Calculs rapides sur les séries, séries différentiellement finies. (Chap. 3 et 14)

Exercices

Cours 3. 27/09

Alin Bostan.

Algèbre linéaire dense : de Gauss à Strassen. (Chap. 8)

Exercices

Cours 4. 04/10

Alin Bostan.

Évaluation-interpolation rapide. Pgcd, résultant. (Chap. 5 et 6)

Exercices

Cours 5. 11/10

Bruno Salvy.

Récurrences linéaires : coefficients constants et fractions rationnelles, coefficients polynomiaux : n-ième terme, n premiers termes. (Chap. 4 et 15)

Exercices.

Cours 6. 18/10

Alin Bostan.

Approximants de Padé et de Padé-Hermite. Matrices creuses. (Chap. 7 et 9)

Exercices.

Cours 7. 25/10

Alin Bostan.

Matrices structurées. Matrices polynomiales. (Chap. 10 et 11)

Exercices.

ATTENTION : PAS DE COURS LES 1/11 ET 8/11 !

Cours 8. 15/11

Alin Bostan.

Solutions polynomiales et rationnelles d'équations différentielles linéaires, de récurrences linéaires. (Chap. 16 et 17)

Exercices.

Cours 9. 22/11

Alin Bostan.

Séance d'exercices.

Exercices de révision

PARTIEL le 29/11

Cours 10. 06/12

Frédéric Chyzak.

Séries hypergéométriques, algorithmes de Gosper, de Zeilberger et de Petkovšek. (Chap. 29)

Exercices.

Cours 11. 13/12

Frédéric Chyzak.

Équations fonctionnelles linéaires et polynômes tordus. (Chap. 30)

ATTENTION : PAS DE COURS LE 20/12

Cours 12. 10/01

Frédéric Chyzak.

Bases de Gröbner pour les fonctions spéciales. (Chap. 23 sec. 2 à 5, 24, 31)

Cours 13. 17/01

Frédéric Chyzak.

Intégration et sommation définies par création téléscopique. (Chap. 32)

Cours 14. 24/01

Alin Bostan.

Calcul formel pour la combinatoire.

Cours 15. 31/01

Alin Bostan.

Intégration des fractions rationnelles : algorithmes et complexité.

ATTENTION : PAS DE COURS LE 07/02

Cours 16. 14/02

Alin Bostan.

Séance d'exercices.

EXAMEN le 28/02

Bibliographie

Quelques ouvrages des années 1990 :

  • D. Cox, J. Little, D. O'Shea, Ideals, Varieties and Algorithms. Undergraduate Texts in Mathematics, Springer Verlag, 2nd edition, 1996.
  • J. von zur Gathen, J. Gerhard, Modern Computer Algebra, Cambridge University Press, 1999.
  • M. Petkovsek, W. Wilf, D. Zeilberger, A=B, A. K. Peters, 1996.
  • K. O. Geddes, S. R. Czapor, G. Labahn, Algorithms for Computer Algebra, Kluwer Academic Publishers, 1992.

Et l'ouvrage plus récent issu des années antérieures de ce cours :

  • A. Bostan, F. Chyzak, M. Giusti, R. Lebreton, G. Lecerf, B. Salvy et É. Schost, Algorithmes Efficaces en Calcul Formel. Imprimé par CreateSpace. Palaiseau : F. Chyzak (auto-édit.), 2017. Aussi disponible au format électronique. https://hal.archives-ouvertes.fr/AECF/.

Équipe pédagogique

A. BostanCRINRIASaclay
F. ChyzakCRINRIASaclay
B. SalvyDRINRIAENS Lyon
 
Universités partenaires Université Paris-Diderot
Université Paris-Saclay
ENS Cachan École polytechnique Télécom ParisTech
ENS
Établissements associés Université Pierre-et-Marie-Curie CNRS INRIA CEA