Course offered in the second semester of M1.
This class shall survey some of the central topics of computer algebra: arithmetics, effective linear algebra, polynomial system solving.
The following topics will be studied:
- Arithmetic(s) — mostly polynomial.
– Representation of polynomials, linear operations (addition, evaluation).
– Multiplication : schoolbook method, Karatsuba method, Toom-Cook method Fast Fourier Transform.
– Division : schoolbook method, Newton method, recursive division
– GCD : Euclidean algorithm, extended GCD, application to CRT; introduction to fast GCD.
– Fast multiple point evaluation, fast interpolation, fast CRT.
– Introduction to multiple precision integer arithmetic, floating-point arithmetic, finite fields arithmetic.
- Linear algebra over a field
– Matrix/vector product, naive matrix/matrix product
– Row echelon form & applications : kernel, image, rank, determinant, linear system solving, etc.
– Fast matrix/matrix product : Strassen ; fast inversion/determinant.
– Structured matrices: circulant, Hankel, Toeplitz, Cauchy, and related algorithms.