Fast Matrix Computations, Jan-Apr 2016

Monday, 3:30PM-5:00PM @ Super Computer Education and Research Center, Room 202

Sivaram Ambikasaran, firstname(dot)lastname@icts(dot)res(dot)in
Office hours: After class till 5:30PM.

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

    3 Jan 25: Fast Fourier transform Lecture3

    Image compression using FFT
    4 Feb 8: Non uniform fast Fourier transform and Generalized Rybicki Press algorithm Lecture4


    5 Feb 22: Generalized Rybicki Press algorithm and Fast Gauss Transform


    6 Mar 7: Fast Multipole Method

    7 Mar 14: Fast Multipole Method & Polynomial interpolation

    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