MTHSC 985   Lecture notes
Clemson University    Fall 2001
Shuhong Gao

Fast Fourier transforms and sparse linear systems over finite fields


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.


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