**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 |