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 :
I. 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.
II. 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