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

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

Responsable : F. Chyzak

Important note: Starting October 12, 2020, and until further notice, all lectures will take place only remotely, on Big Blue Button. See this year's calendar below. Students who intend to follow the lectures should contact the professors as soon as possible to get the proper BBB invitation.

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) et Analyse d'algorithmes (2-15).

Plan du cours, horaires et intervenants prévus pour 2020-2021

  • Première période : Algorithmes fondamentaux
  • Deuxième période : Sommation et intégration de suites et fonctions spéciales

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.

Horaire et lieu pour 2020-2021

Edit, 2020-09-28: all lectures will happen on Big Blue Button.

Le lundi, 16h15-19h15, en salle 1014.

Intervenants
Langues du cours, notation, documents autorisés

For the year 2020-2021, the lectures will be in English, with as much material in English as possible. The book will not be translated; English references (below) cover part of the book.

Selon la terminologie du MPRI, il s'agit d'un module « French by default », c'est-à-dire que le cours oral est enseigné en français, sauf si au moins un étudiant non francophone préfère l'anglais sans qu'aucun élève francophone n'exige le français. Néanmoins, le livre servant de référence au cours est rédigé totalement en français ; par ailleurs, certains cours, en français à l'oral, seront donnés sur transparents, lesquels seront écrits en anglais. Dans tous les cas, les étudiants sont autorisés à rédiger leurs examens en français ou en anglais.

Sauf pour le cas d'élève choisissant officiellement de ne suivre qu'une moitié du module (cours sécable), la note du cours sera la moyenne des notes obtenues au partiel et à l'examen final. Les documents autorisés aux examens sont le livre du cours et les notes de cours de l'étudiant.

Livre : AECF

Séance 1. 21/09

F. Chyzak

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

Séance 2. 28/09

A. Bostan

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

Séance 3. 5/10

F. Chyzak

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

Séance 4. 12/10

A. Bostan

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

Séance 5. 19/10

F. Chyzak

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

Séance 6. 26/10

A. Bostan

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

Séance 7. 2/11

A. Bostan

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

ATTENTION : PAS DE SÉANCE LE 9/11 !

Distribution des exercices pour le 16/11

Séance 8. 16/11

A. Bostan

Exercices de révision.

ATTENTION : PAS DE SÉANCE LE 23/11 !

EXAMEN SUR LA PREMIÈRE PÉRIODE LE 30/11

Séance 9. 7/12

F. Chyzak

Séries hypergéométriques, algorithmes de Gosper, de Zeilberger et de Petkovšek. (Chap. 29 et un bout du Chap. 16) Slides Exercices

ATTENTION : PAS DE SÉANCE LE 14/12 !

Séance 10. 04/01

F. Chyzak

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

Séance 11. 11/01

F. Chyzak

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

Séance 12. 18/01

F. Chyzak

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

Séance 13. 25/01

F. Chyzak

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

Séance 14. 1/02

A. Bostan

Diagonals and Creative Telescoping — From 1G to 4G algorithms.

Séance 15. 8/02

A. Bostan

Calcul formel pour la combinatoire.

ATTENTION : PAS DE SÉANCE LE 15/02 !

Séance 16. 22/02

A. Bostan

Exercices de révision.

EXAMEN SUR LA DEUXIÈME PÉRIODE LE 8/03

Bibliographie

Quelques ouvrages des années 1990-2000 :

  • 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 gratuitement au format électronique. https://hal.archives-ouvertes.fr/AECF/.

Équipe pédagogique

A. BostanCRINRIASaclay
F. ChyzakCRINRIASaclay
 
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