Fast Fourier transforms and sparse linear systems over
finite fields
Outline:
Fast Fourier transforms, fast multiplication of polynomials (integers), fast decoding of RS codes, sparse linear systems (from coding theory, cryptography and computer algebra), Krylov subspace methods (Lanczos and bi-orthogonal methods), Wiedemann's method a la Berlekamp-Massey, block algorithms (Coppersmith's and Montgomory's) and their analysis.
Contents:
Lecture 1: Sparse linear systems in practice (pdf file, 58k)
Lecture 2: Chinese Remainder Theorem (CRT) and interpolation (pdf file, 56k)
Lecture 3: Fast Fourier Transforms (pdf
file, 98k)
Lecture 4: Additive Fast Fourier Transforms (available soon).
Lecture 5: Fast multiplication of polynomials