INFO4218 : Calcul formel
Computer algebra
- Responsable(s) :
-
- Daniel Hirschkoff
- Enseignant(s) :
-
- Gilles Villard
- Bruno Salvy
Niveau
M1+M2
Discipline
Informatique
ECTS
3.00
Période
2e semestre
Département
Localisation
Site Monod
Année
2024
Public externe (ouverts aux auditeurs de cours)
Informations générales sur le cours : INFO4218
Content objectif
Computer Algebra is the art of using a computer to perform exact mathematical computations.
This course will cover the following notions:
- Fast multiplication (Karatsuba, FFT);
- Fast division (symbolic Newton iteration, evaluation-interpolation);
- Euclidean algorithm (gcd and applications, fast gcd);
- Resultant (elimination in two variables);
- D-finite power series (automatic proofs of identities);
- linear algebra (fast matrix multiplication and equivalent problems);
- linear algebra over polynomial matrices (minimal bases and applications);
- symbolic summation (Gosper’s algorithm, Zeilberger’s algorithm, Petkovsek’s algorithm);
- Gröbner bases (algorithms for polynomial systems and applications).
The aim of this course is to cover these fundamental algorithms while providing the students with a practical familiarity with their uses and applications through tutorials using Maple. After this course, no student will think of using pen-and-paper for long mathematical derivations.
Content prerequis
Basic knowledge of algebra, algorithms, complexity analysis and programming.
Content bibliographie
References for this course, but sometimes at a more advanced level, are:
- Modern Computer Algebra, by Joachim von zur Gathen and Jürgen Gerhard;
- Algorithmes Efficaces en Calcul Formel, by Alin Bostan, Frédéric Chyzak, Marc Giusti, Romain Lebreton, Grégoire Lecerf, Bruno Salvy et Éric Schost. (Available for free.)