University of Texas at Austin, Spring 2022:
MATH 397 C: Fast Algorithms - Theory & Practice

Instructor:
Gunnar Martinsson. Room: PMA 11.164 Email: pgm@oden.utexas.edu

Meeting times:
Tuesdays and Thursdays, 12:30 - 13:45, PMA 11.176.

Website:
https://users.oden.utexas.edu/~pgm/Teaching/2022_fast_algorithms/

Syllabus:
pdf

Description:
The course will describe efficient algorithms for solving large scale problems that arise in scientific computing and data science. The focus will be on linear algebraic problems such as solving linear systems, finding eigenvalues and eigenvectors, and computing low rank approximations to large matrices. Parts of the course material will be targeted specifically towards linear problems that arise upon the discretization of partial differential equations. We will discuss topics such as algorithmic complexity, numerical stability, and how to minimize communication in designing algorithms.

Examination:
60% on homeworks, 40% on final exam, see syllabus.

Schedule:

Week:	Homework:	Material covered:
1 (Jan 18)		Tue: Intro, and review of linear algebra. Thu: Intro, and review of linear algebra.
2 (Jan 25)		Tue: Krylov methods. Thu: Krylov methods.
3 (Jan 31)		Tue: Krylov methods. Matlab demos: arnoldi, gmres, cg. Thu: Class canceled due to snow.
4 (Feb 7)	Homework 1 due on Thursday.	Tue: Krylov methods. Thu: Krylov methods. Preconditioning.
5 (Feb 14)	Homework 1 due on Tuesday. The file hw01_p2.m	Tue: Randomized methods in linear algebra. Thu: Randomized methods in linear algebra.
6 (Feb 21)		Tue: Randomized methods in linear algebra. Zoom! Thu: Randomized methods in linear algebra.
7 (Feb 28)	Homework 2 due on Thursday. hw02p3.m, hw02p4.m, hw02p6.m.	Tue: Sampling. Johnson-Lindenstrauss theory. Thu: FFT and transform based methods.
8 (Mar 7)		Tue: FFT and transform based methods. Thu: FFT and transform based methods. main_fft.m; main_fft_speed.m; main_fourier_series.m.
Spring break
9 (Mar 21)		Tue: FFT and transform based methods. Thu: Sparse linear algebra.
10 (Mar 28)	Homework 3 due on Thursday.	Tue: Sparse linear algebra. Thu: Iterative methods and multigrid.
11 (April 4)		Tue: Iterative methods and multigrid. Thu: (Iterative methods and multigrid. No class.)
12 (April 11)		Tue: The Fast Multipole Method. Thu: The Fast Multipole Method. Slides for Thursday lecture.
13 (April 18)	Homework 4 due on Thursday.	Tue: Adaptive FMM. Rank structured matrices. Thu: Rank structured matrices. Slides for Tuesday lecture.
14 (April 25)		Tue: Boundary integral equations. Thu: Boundary integral equations. Slides for Thursday lecture.
15 (May 2)	Homework 5 due on Thursday. Matlab codes.	Tue: (Newton solvers.) Review. Thu: (Newton solvers.) Review.
Finals week (May 9)		Final exam on Saturday May 14, 9:00am - noon. Will be delivered via GradeScope.

Resources:

• Recommended reference for randomized linear algebra, fast multipole method, boundary integral equations, and rank structured matrices:
  P.G. Martinsson,
  "Fast Direct Solvers for Elliptic PDEs"
  SIAM book store.


• Recommended reference for Krylov methods:
  Lloyd N. Trefethen and David Bau, III,
  "Numerical Linear Algebra"
  SIAM book store.


• Tutorial on randomized methods.
  P.G. Martinsson,
  "Randomized methods for matrix computations."
  Arxiv.org report #1607.01649, 2018.


• Recommended reading on methods for sparse matrices.
  Tim Davis,
  "Direct Methods for Sparse Linear Systems."
  SIAM, 2006.


• Survey paper on randomized methods for low rank approximation.
  N. Halko, P.G. Martinsson, J. Tropp,
  "Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions."
  SIAM Review, 53(2), 2011, pp. 217-288.


• Link to material for a summer school taught in 2016. The exercises and tutorial codes may be useful:
  http://amath.colorado.edu/faculty/martinss/2016_PCMI/