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.

Professors for 2023-2024: Alin Bostan, Pierre Lairez, Marc Mezzarobba, Vincent Neiger.

Warning: this course is starting on September 21. There is no lecture on September 14.

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.

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 (Polynomial Systems, computer algebra, and applications 2-13-1), Codes correcteurs d'erreurs et applications à la cryptographie (Error correcting codes and applications to cryptography 2-13-2), Techniques en cryptographie et cryptanalyse (Techniques in cryptography and cryptanalysis 2-12-1), Algorithmes arithmétiques pour la cryptologie (Arithmetic algorithms for cryptology 2-12-2) and Analyse d'algorithmes (Analysis of algorithms 2-15).

Organization for 2023-2024

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 2023-2024

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

Professors
Alin Bostan Inria Saclay
Pierre Lairez Inria Saclay
Marc Mezzarobba CNRS
Vincent Neiger Sorbonne Université
Language

Summary: English spoken if requested, otherwise French spoken; all slides in English; book in French.

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 (in most recent years, the course has been fully taught in 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.

Periods and evaluation

Except for students who will officially choose 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.

The course is breakable, so that students may elect not to attend the second period (thus validating only half of the ECTS). We strongly recommend against attending the second period only, without the first one.

Book: AECF

Other useful references can be found at the end of this webpage.

Lecture 1. 21/09

Vincent Neiger

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

Documents

Lecture 2. 28/09

Alin Bostan

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

Slides Exercises

ATTENTION: NO LECTURE ON 05/10!

Lecture 3. 12/10

Alin Bostan

Fast evaluation and interpolation. Gcd and extended gcd. (Chapters 5 and 6)

Slides Exercises

Lecture 4. 19/10

Alin Bostan

Resultants. Fast computations with power series via Newton iteration. (Chapters 3 and 6)

Slides Exercises

Lecture 5. 26/10

Marc Mezzarobba

D-finite power series. (Chapter 14)

Slides Exercises

Lecture 6. 02/11

Marc Mezzarobba

Linear recurrences with constant coefficients: link with rational functions, n-th term, first n terms; linear recurrences with polynomial coefficients: arithmetic complexity of n-th term. (Chapters 4 and 15)

Slides Exercises

Lecture 7. 09/11

Marc Mezzarobba

Linear recurrences with polynomial coefficients: binary complexity of n-th term, sums of differentially finite power series. Series, polynomial and rational solutions of linear differential equations. (Chapters 15, 16, 17)

Slides Exercises

Lecture 8. 16/11

Tutorial/Exercises session.

FIRST-PERIOD EXAM ON 23/11

Some rules: The consultation of static data (lecture slides, personal notes, computer algebra books, ...) 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.

ATTENTION: NO LECTURE ON 30/11!

Lecture 9. 07/12

Vincent Neiger

Computations with polynomial matrices: introduction and motivations.

Slides Exercices Solutions

Lecture 10. 14/12

Vincent Neiger

Polynomial matrices: fast Hermite-Padé approximation and vector interpolation.

Slides Exercises Some SageMath code Solutions

SageMath documentation for univariate polynomial matrices

Lecture 11. 21/12

Vincent Neiger

Fast divide and conquer vector interpolation, and a selection of applications.

Slides

Lecture 12. 11/01

Pierre Lairez

Polynomial factorization over finite fields. (Chap 19)

Slides Exercises Notebook sagemath

Lecture 13. 18/01

Pierre Lairez

Factorization over the integers. (Chapters 20 and 21)

Slides Notebook sagemath

Lecture 14. 25/01

Pierre Lairez

Lattice reduction. Application to factorisation and experimental mathematics.

slides Notebook sagemath Some zeros of the zeta function

Lecture 15. 01/02

Pierre Lairez

Lecture 16. 08/02

Alin Bostan

Computer algebra for combinatorics.

Slides

ATTENTION: NO LECTURE ON 15/02!

ATTENTION: NO LECTURE ON 22/02!

SECOND-PERIOD EXAM ON 29/02

In recent years, the second-period exam consisted in a presentation of a research article, followed by some questions by the course teachers. The research article was chosen by the student a few weeks before, from a list provided by the teachers.

Bibliography

General works:

  • 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.
  • D. Cox, J. Little, D. O'Shea, Ideals, Varieties and Algorithms. Undergraduate Texts in Mathematics, Springer Verlag, 2nd edition, 1996.

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