MTHSC 985   Lecture notes
Clemson University    Fall 2001
Shuhong Gao

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