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

Efficient Algorithms in Computer Algebra (48h, 6 ECTS)

French title: Algorithmes efficaces en calcul formel.

In charge: F. Chyzak

Important note: dates of sessions from December 9, 2021 on have been changed.

Objectives

Computer Algebra (also known as Symbolic Computation, or Calcul formel in French) consists in developing computer representations and manipulations of mathematical objects in an exact way, in contrast with traditional scientific computing, for example. As a counterpart of such exact algebraic representations, computation times are often large and memory requirements are often huge if one employs naive algorithms. In this course, we introduce basic computer-algebra algorithms to work with polynomials, series, and matrices, so as to achieve in many cases quasi-optimal complexity bounds. Such algorithms are largely used in practice in computer-algebra systems, but as well in several other modern algorithmic domains that rely on algebraic techniques, such as cryptography, multivariate cryptoanalysis, and error-correcting codes.

In a second part of the course, we enter more specialized, active research domains, including symbolic summation and integration. The symbolic summation and integration methods that we describe have become unexpendable computation tools for physics, the numeric evaluation of special functions, the modelling of combinatorial problems, and more broadly for difficult questions of formulas simplification.

This course is particularly well suited to those who wish to rigorously understand the algorithmic foundations of algebraic calculation and their general principles, as a supplement of the courses 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) and Analyse d'algorithmes (2-15).

Organization for 2021-2022

This webpage holds the contents of the whole course and will be updated on a weekly basis to integrate various notes and documents, and potentially to reflect evolutions based on what could be presented during lectures.

Time and location for 2021-2022

On Thursdays, 16:15-19:15, room 1002.

Professors
Language

Summary: French spoken, unless English requested; all slides in English; book in French will not be translated.

In line with the MPRI terminology, the course is a module “English upon request”, meaning that (oral) lectures will be in French, unless at least one non-French-speaking student requests English. Nevertheless, our main reference book was written in French and will not be translated. In all lectures, whatever the spoken language, slides will be written in English. In all cases, students will be allowed to take their exams in French or English. (The year 2020-2021 was fully taught in English.)

Except for students who will officially chose to quit the course after the first half (“breakable module”), the global mark will be an average between the marks for the first and second halves of the course. Documents allowed during examinations will be the book and personal notes by the student.

The course is breakable, so that student may elect to not attend the second period (thus validating only half of the ECTS), but we strongly discommend attending the second period only.

Book: AECF

Lecture 1. 23/09

F. Chyzak

General presentation of the course. Fast polynomial multiplication. (Chapters 1 and 2) Slides Exercises

Lecture 2. 30/09

A. Bostan

Dense linear algebra: from Gauss to Strassen. (Chapter 8) Slides Exercises

Lecture 3. 07/10

A. Bostan

Fast evaluation and interpolation. Gcd and resultant. (Chapters 5 and 6) Slides Exercises

Lecture 4. 14/10

F. Chyzak

Fast computations with series. D-finite power series. (Chapters 3 and 14) Slides Exercises

Lecture 5. 21/10

F. Chyzak

Linear recurrences: constant coefficients and rational functions, polynomial coefficients: n-th term, first n terms. (Chapters 4 and 15) Slides Exercices

Lecture 6. 28/10

V. Neiger

Computations with polynomial matrices: introduction and motivations. Slides Exercices Solutions to last week's exercises

Lecture 7. 04/11

P. Lairez

Polynomial factorization over finite fields. (Chap 19) Slides Exercises Solutions to last week's exercises

ATTENTION: NO LECTURE ON 11/11!

Lecture 8. 18/11

A. Bostan

ATTENTION: NO LECTURE ON 25/11!

FIRST-PERIOD EXAM ON 2/12

Some rules: The consultation of static data (lessons and personal notes) on an electronic device is authorized, provided that these devices are not connected to any network. Consultation of the course and personal notes on paper is authorized.

First-period exam of 2013 (in French)

ATTENTION: NO LECTURE ON 09/12!

Lecture 9. 16/12

V. Neiger

Polynomial matrices: fast approximation and interpolation, quasi-linear GCD. Slides Exercises

Lecture 10. 06/01

V. Neiger

Using approximation and interpolation for kernel bases, quasi-linear gcd, and other applications. Slides Exercises

Lecture 11. 13/01

P. Lairez

Factorization over the integers, lattice reduction. (Chapters 20 and 21) Slides Notebook sagemath

Lecture 12. 20/01

F. Chyzak

Polynomial and rational solutions of linear ODEs and OREs. (Chapters 16 and 17) Slides Exercises

Lecture 13. 27/01

F. Chyzak

Gosper's, Zeilberger's, Almkvist and Zeilberger's algorithms. Algorithms by compact forms. (Chapter 29 and part of Chapter 16) Slides Exercise

ATTENTION: NO LECTURE ON 3/02!

Lecture 14. 10/02

P. Lairez

Binomial sums and diagonals. Slides Exercices Maple worksheet

Lecture 15. 17/02

A. Bostan

Computer algebra for combinatorics. Slides

Lecture 16. 24/02

A. Bostan

Exercises session.

ATTENTION: NO LECTURE ON 03/03!

SECOND-PERIOD EXAM ON 10/03

Bibliography

General works:

  • 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.

The book emanating from our lectures over the past years:

  • A. Bostan, F. Chyzak, M. Giusti, R. Lebreton, G. Lecerf, B. Salvy and É. Schost, Algorithmes Efficaces en Calcul Formel. Printed by CreateSpace. Palaiseau: F. Chyzak (self-ed.), 2017. Also available for free in electronic format. https://hal.archives-ouvertes.fr/AECF/.

Pedagogical team

A. BostanDRInria Saclay ÎDF
F. ChyzakCRInria Saclay ÎDF
P. LairezCRInria Saclay ÎDF
V. NeigerMdCSorbonne Université
 
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