Venue:
Monday, 3:30PM-5:00PM @ Super Computer Education and Research Center, Room 202
Instructor:
Sivaram Ambikasaran, firstname(dot)lastname@icts(dot)res(dot)in
Office hours: After class till 5:30PM.
Syllabus:
The course will provide an introduction to fast algorithms for matrix computations and their applications in computational science. The topics covered will include generalised Rybicki Press algorithm, uniform and non-uniform fast Fourier transform, fast Laplace and Gauss transforms, fast multipole method, low-rank factorisations and hierarchical matrix based matrix vector products, iterative & direct solvers for sparse & dense matrices. We will draw material from approximation theory, asymptotic expansions, linear algebra and graph theory. Applications will include solution of partial differential & integral equations and computational statistics.
Flyer for the course
Prerequisite texts:
| Week | Lecture notes/slides | Additional material/Homework |
| 1 | Jan 11: Introduction to matrix computations Lecture 1 | Gauss elimination is not optimal A non-commutative algorithm for multiplying \(3 \times 3\) matrices using \(23\) multiplications |
| 2 | Jan 18: Matrix decompositions and solvers Lecture2 | The Smart Money’s on Numerical Analysts Assignment |
| 3 | Jan 25: Fast Fourier transform Lecture3 | Assignment Image compression using FFT |
| 4 | Feb 8: Non uniform fast Fourier transform and Generalized Rybicki Press algorithm Lecture4 |
NUFFT_1 NUFFT_2 Assignment |
| 5 | Feb 22: Generalized Rybicki Press algorithm and Fast Gauss Transform |
GRP FGT FGT_Remarks |
| 6 | Mar 7: Fast Multipole Method |
FMM BBFMM |
| 7 | Mar 14: Fast Multipole Method & Polynomial interpolation |
Lecture7 Function Approximation |
| 8 | Mar 28: Interpolation based low-rank contruction |
Fundamental theorem of polynomial interpolation |
| 9 | April 18: Optimality of Chebyshev/Legendre interpolation nodes, low-rank construction methods and HODLR solver |
Optimality of Chebyshev interpolation nodes Optimality of Legendre interpolation nodes Low-rank construction Low-rank & HODLR solver |