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 and also in several other modern algorithmic domains that rely on algebraic techniques, such as cryptography, multivariate cryptanalysis, 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 Codes correcteurs d'erreurs et applications à la cryptographie (Error correcting codes and applications to cryptography CODES), Cryptographie basée sur les réseaux euclidiens (Lattice-based Cryptography and Cryptanalysis LCRYPT), Algorithmes arithmétiques pour la cryptologie (Arithmetic algorithms for cryptology CRYPTALG) and Analyse d'algorithmes (Analysis of algorithms AOFA).

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.

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

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

In line with the MPRI terminology, the course is “in English upon request”, meaning that lectures will be in French, unless one or more non-French-speaking student requests English (in recent years, the course has been often fully taught in English). One main reference book of the course 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 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.

Except for students who will officially choose to quit the course after the first half, the global mark will be an average between the marks for the first and second halves of the course.

Book (pdf version freely available): AECF

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

Introduction. Extended Euclidean algorithm. Fast polynomial multiplication.

Slides & SageMath code

Dense linear algebra: from Gauss to Strassen, and some recent developments.

Slides Exercices

Newton iteration for power series, fast polynomial division, fast evaluation and interpolation.

Slides Exercices

C-recursive sequences: Nth term and first N terms. Application to power series composition.

Slides Exercices

Computations with polynomial matrices: introduction, motivations, and basic algorithms.

Slides & Exercises

Using polynomial matrices I: approximation and interpolation, structured matrices, and fast GCD.

Slides, SageMath Code, Exercises

D-finite power series.

Special session: Tutorial / Exercises / Exam preparation.

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.

Solutions of linear differential equations.

Definite summation and integration.

Multivariate polynomials, division and ideal membership problems.

Gröbner bases and the Buchberger algorithm.

Linearization and the F4 algorithm.

Regularity and complexity analysis through generating series.

Using polynomial matrices II: Hermite Normal form and Gröbner basis change of order.

Opening: applications of computer algebra.

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.

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