# Fast Matrix Computations, Jan-Apr 2016

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:

• Numerical Linear Algebra, by Lloyd N. Trefethen and David Bau III
• Matrix Computations, Gene H. Golub and Charles F. Van Loan
• ## Calendar

 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