M1-level course at ENS-Lyon with Gilles Villard. Computer Algebra is the art of using a computer to perform exact mathematical computations. The aim of this course is to cover the fundamental algorithms of this field (from the Fast Fourier Transform to Gröbner bases), while providing the students with a practical familiarity with its uses and applications through tutorials using Maple. After this course, no student will think of using pen-and-paper for long mathematical derivations. See the web site.
Modern Algorithms for Symbolic Summation and Integration
M2-level course at ENS-Lyon with Alin Bostan and Gilles Villard. Computer Algebra, or Symbolic Computation, represents and manipulates mathematical objects on a computer in an exact way, in contrast with the traditional scientific computing. In this course, we present a very active research topic in Computer Algebra – the development of algorithms for symbolic summation and symbolic integration. The emergence of these algorithms has put an important family of computational tools in the hands of discrete mathematicians, and many results that were unaccessible in other ways have been found and proved by computer methods. These algorithms are also nowadays unavoidable in physics, for the numerical evaluation of special functions, and more broadly for the difficult questions of simplification of formulas. See the web site.
Design and Analysis of Algorithms
Course for the 2nd year bachelor students at Ecole polytechnique on the design and analysis of algorithms. It insisted on important paradigms in algorithm design, illustrating the ideas through many examples and introducing data structures when needed. As much as possible, the examples are implemented in Python, with which the students experiment. It covers divide-and-conquer algorithms, randomization, amortization, balancing, string algorithms and P vs. NP. See the web site.
Logic, Models, Computation
An interesting course given by Olivier Bournez at École polytechnique, where I had a small participation. See the web site.
Efficient algorithms for computer algebra
M2-level course at MPRI. Computer algebra (also called symbolic computation) studies the computer representation and handling of mathematical objects. The objects are represented in an exact way. The price to pay is an explosion of the memory size required by the computations. In this course, we give a presentation of the basic algorithms of computer algebra with a focus on quasi-optimal algorithms. These algorithms are then applied to active research themes like summation, integration and effective commutative algebra. This is a course we set up and started in 2004, with (depending on the year) Alin Bostan, Frédéric Chyzak, Marc Giusti, Eric Schost. I leaved the team in 2019. Detailed course notes of about 700 pages are now available as a book, available for free on its web site.
Algorithmes pour les Mathématiques Expérimentales
Euler, Gauss, Ramanujan et de nombreux autres calculaient énormément d’exemples à de grandes précision pour raffiner leur intuition des phénomènes qu’ils étudiaient. Le mathématicien hongrois George Pólya disait quant à lui “Finished mathematics consists of proofs, but mathematics in the making consists of guesses”. Aujourd’hui, les systèmes de calcul formel allègent énormément la charge de calcul, et permettent de ce fait d’atteindre des exemples qui ne soient pas de simples jouets. Cette possibilité change la donne. Ainsi, une vieille conjecture de combinatoire a été résolue récemment par des expériences de grande taille, menant d’abord à une conjecture sur l’algébricité d’une série, puis à une preuve informatisée sur des polynômes de degré énorme; les records récents de calculs de décimales de \(\pi\) reposent quant à eux sur une formule découverte expérimentalement en 1995, puis prouvée facilement. Dans tous ces cas, il faut cependant connaître et maîtriser quelques outils de base pour tirer le meilleur parti des possibilités qu’apportent les ordinateurs dans ce domaine. Le cours se compose de séances au tableau le matin, suivies d’après-midis consistant à réaliser une expérience sur un sujet lié à un outil présenté le matin. Les étudiants conçoivent eux-mêmes des expériences qu’il réalisent dans les dernières séances. Voir la page web du cours.
Design and Analysis of Algorithms
A classical introductory course taught by Benjamin Doerr at École polytechnique, where I gave “petites classes”. I have also given programming projects on weak secret keys, fast evaluation of constants and sampling very large data.
Approximations: from symbolic to numerical computations, and applications
M2-level course at ENS-Lyon with Nicolas Brisebarre. This course covers part of approximation theory from the point of view of effective computation. Computation of polynomial or rational approximants, efficient computation of Taylor series expansions or series expansions based on families of orthogonal polynomial, use of these expansions to produce approximations to a prescribed accuracy (Remez’ algorithm, Taylor and Chebyshev models). The power of these techniques is illustrated with three applications from different scientific domains: irrationality proofs in number theory, efficient evaluation of numerical functions, computational issues related to Near-Earth Objects. This was set up and given in Fall 2012 and Fall 2013. A first version of the course notes is available from the site of the course.
A nice M1-level course on computer algebra oriented towards experimental mathematics at École Normale Supérieure with Alin Bostan. It is the ancestor of the course with the same title at Ecole polytechnique. Computer algebra studies the computer handling of exact mathematical objects. This course develops the use of high-precision approximations as an intermediate data-structure for the representation of exact objects. We give an overview of the main tools letting one pass from equations, sums or integrals to good approximations (hundreds of digits or coefficients depending on the cases), then conversely, starting from approximations, reconstructing the equations they solve in an approximate way or of ``exact formulas’’ they approximate. High-precision approximations are often sufficient for the expressions reconstructed that way to be exact. We conclude with a presentation of algorithms for the proof of identities for algebraic numbers, hypergeometric series, or more general D-finite series, or answering questions on the solution of polynomial systems. Beyond an understanding of algorithmic tools, the course insists on their use and a large part of it takes place in front of a computer.
Analysis of Algorithms
M2-level course that was created by Philippe Flajolet and that I was co-teaching with him for a few years.
- A short presentation on computer algebra and average-case complexity analysis in that same course more recently.
- An introduction to Maple in 2 times 2 hours for students preparing the French “agrégation”.
- Even earlier, I gave an introduction to computer algebra in the DEA Algorithmique; and a course on ``Computer algebra, special functions and combinatorial identities’’ in the DEA Informatique Fondamentale et Applications.
- In the ancient past, I’ve also done some teaching (for 7 years!) at the École polytechnique.
With several colleagues from the AriC group, we have animated a L3-level reading group, where students give a course based on a chapter or a portion of a chapter of a book each week.