Computer Algebra

Course offered in the second semester of M1.

contents:

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:

  1. 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.
  2. 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.