Liens transverses ENS de Lyon

INFO4218 : Calcul formel

Computer algebra

Niveau M1+M2

Discipline(s) Informatique

ECTS 3.00

Période 2e semestre

Localisation Site Monod

Année 2021-2022

 Public externe (ouverts aux auditeurs de cours)

Objectif du cours

Computer algebra, a.k.a. symbolic computation, is a broad transdisciplinary area which aims at computerizing mathematics, i.e. solving exactly mathematical problems, using computers. Hence, it encompasses effective mathematics in algebra, analysis, geometry and number theory, the design of algorithms, the study of their complexities, their implementations and their use in applications, as well as software system aspects to manipulate and encode efficiently mathematical objects.

This class covers the core topics of computer algebra with a view towards their application to concrete questions that may arise in mathematically oriented activities. 

The following topics will be studied :

– Fast multiplication (Karatsuba, Toom-Cook, Fast Fourier Transform);

– Newton's iteration in a symbolic context: fast division; Euclidean division; evaluation and interpolation;

– Euclid: Euclidean algorithm; extended gcd; rational reconstruction; Padé approximants;

– Fast linear algebra: matrix inversion, system resolution;

– Resultants: definitions, properties and applications;

– Polynomial matrices: algorithms and applications;

– D-finite power series;

– Hypergeometric summation;

– Gröbner bases: definitions, properties and applications.

Each lecture will be complemented by a tutorial in Maple, exploring questions that can be solved with the algorithms seen in class.


No specialized knowledge is required.


The course consists of 11 2h-long lectures and as many tutorials on computers.

 J. von zur Gathen, J. Gerhard, Modern Computer Algebra, Cambridge University Press, 1999.

Modifié le :
07/07/2021 06:23:31