Table of Contents
Efficient Algorithms in Computer Algebra (48h, 6 ECTS)French title: Algorithmes efficaces en calcul formel. Professors for 20242025: Alin Bostan, Pierre Lairez, Marc Mezzarobba, Vincent Neiger. ObjectivesComputer 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 computeralgebra algorithms to work with polynomials, series, and matrices, so as to achieve in many cases quasioptimal complexity bounds. Such algorithms are largely used in practice in computeralgebra systems, but as well in several other modern algorithmic domains that rely on algebraic techniques, such as cryptography, multivariate cryptoanalysis, and errorcorrecting 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 2131), Codes correcteurs d'erreurs et applications à la cryptographie (Error correcting codes and applications to cryptography 2132), Techniques en cryptographie et cryptanalyse (Techniques in cryptography and cryptanalysis 2121), Algorithmes arithmétiques pour la cryptologie (Arithmetic algorithms for cryptology 2122) and Analyse d'algorithmes (Analysis of algorithms 215). Organization for 20242025This 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 20242025On Mondays, 16:1519:15, room 1004. Exception: course on Thursday 14 November, 16:1519:15, room 1004. Professors
LanguageSummary: 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 nonFrenchspeaking 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 evaluationExcept 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. 23/09Vincent NeigerGeneral presentation of the course. Fast polynomial multiplication. (Chapters 1 and 2) ATTENTION: NO LECTURE ON 30/09!Lecture 2. 07/10Vincent NeigerDense linear algebra: from Gauss to Strassen. (Chapter 8) Lecture 3. 14/10Marc MezzarobbaDfinite power series. (Chapter 14) Lecture 4. 21/10Alin BostanLecture 5. 28/10Alin BostanGcd, resultant. Fast computations with power series via Newton iteration. (Chapters 3 and 6) Lecture 6. 04/11Alin BostanLinear recurrences with constant coefficients and rational functions: nth coefficient + fast composition of power series Lecture 7. 14/11 (Thursday, 16.1519.15)Vincent NeigerComputations with polynomial matrices: introduction and motivations. Slides (these are slides from a previous year, which will be updated after the lecture) Lecture 8. 18/11Tutorial/Exercises session. FIRSTPERIOD EXAM ON 25/11 OR 02/12Some 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. Lecture 9. 09/12Vincent NeigerFast approximant bases and uses for sparse and structured linear algebra. Lecture 10. 16/12Pierre LairezPolynomial factorization over finite fields. (Chap 19) Lecture 11. 06/01Pierre LairezPolynomial factorization over the integers (Chapters 20 and 21) Lecture 12. 13/01Pierre LairezLattice reduction. Application to factorisation and guessing. Lecture 13. 20/01Pierre LairezBinomial sums. Lecture 14. 27/01Marc MezzarobbaLinear recurrences with polynomial coefficients: nth term, first n terms. (Chapters 4 and 15) Lecture 15. 03/02Marc MezzarobbaSolutions of linear differential equations. (Chapter 17) Lecture 16. 10/02Alin BostanComputer algebra for combinatorics. ATTENTION: NO LECTURE ON 17/02!ATTENTION: NO LECTURE ON 24/02!SECONDPERIOD EXAM ON 03/03In recent years, the secondperiod 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. BibliographyGeneral works:
The book emanating from our lectures over the past years:
