Intro to Circulant matrices and the FFT, part 1 - Kyle Kloster

Kyle Kloster, Purdue University Math Department PUNLAG is a student-led seminar in numerical linear algebra at Purdue University. Circulant matrices enjoy a special structure with connections to roots of unity and Krylov matrices. We'll define circulant matrices and look at how these connections enable O(N) storage (!) and O(N log N ) matrix-vector products for circulant, as well as the related Toeplitz, and Hankel matrices. This video will be continued in part 2