Table of Contents
Efficient Algorithms in Computer Algebra (48h, 6 ECTS)French title: Algorithmes efficaces en calcul formel. In charge: 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 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 (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 2022-2023This 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 2022-2023On Tuesdays, 12:45-15:45, room 1004. ProfessorsLanguageSummary: 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 (from 2020 until now, 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 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 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. Book: AECF Other useful references can be found at the end of this wepage. Lecture 1. 20/09Vincent NeigerGeneral presentation of the course. Fast polynomial multiplication. (Chapters 1 and 2) Documents Lecture 2. 27/09Alin BostanDense linear algebra: from Gauss to Strassen. (Chapter 8) Slides Lecture 3. 04/10Alin BostanFast evaluation and interpolation. Gcd and extended gcd. (Chapters 5 and 6) Slides Lecture 4. 11/10Alin BostanResultant. Newton iteration. (Chapters 3 and 6) Slides Lecture 5. 18/10Alin BostanD-finite power series. (Chapter 4) Slides Slides (Newton iteration, part 2) Lecture 6. 25/10Alin BostanComputing terms of linearly recurrent sequences. (Chapters 4 and 15) Slides (C-recursive case) Slides (P-recursive case) ATTENTION: NO LECTURE ON 01/11!Lecture 7. 08/11Vincent NeigerLecture 8. 15/11Alin BostanExercises session. ATTENTION: NO LECTURE ON 22/11!FIRST-PERIOD EXAM ON 29/11Some 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. Lecture 9. 06/12Vincent NeigerLecture 10. 13/12Vincent NeigerPolynomial matrices: fast approximation/interpolation and applications Lecture 11. 03/01Pierre LairezATTENTION: NO LECTURE ON 10/01!Lecture 12. 17/01Pierre LairezFactorization over the integers. Lecture 13. 24/01Pierre LairezNo lecture on 31/01Cancelled due to social movement against pension reform (Projet de réforme des retraites 2023). Lecture 14. 07/02Pierre LairezBinomial sums (continued) and symbolic integration. Lecture 15. 14/02Alin BostanComputer algebra for combinatorics. ATTENTION: NO LECTURE ON 21/02!SECOND-PERIOD EXAM ON 28/02BibliographyGeneral works:
The book emanating from our lectures over the past years:
Pedagogical team
|