Meeting times:
Tuesdays and Thursdays, 11:00 - 12:30.
Website:
http://users.ices.utexas.edu/~pgm/Teaching/2019_393C/
Syllabus:
pdf
Description:
The class will describe analysis based computational techniques
for rapidly and accurately solving some of the key tasks
encountered in scientific computing. We will
cover methods for solving equations that arise in molecular
biology, radar scattering and medical imaging, electrostatics,
astrophysics, mechanical engineering, and many other fields.
The equations we study (Laplace, Helmholtz, linear elasticity,
Stokes, Maxwell, etc) often form the core of a
computational model, and the speed with which they can be
solved is often what decides how realistic of a computational
model can be used.
The course will also cover a range of topics in numerical linear algebra such as Krylov solvers, randomized algorithms for low-rank approximation, and algorithms for so called ``rank-structured'' matrices. These techniques are very useful in the study of fast solvers for elliptic PDEs, but have also found plenty of use in data analysis and other applications.
Examination:
60% on homeworks, 40% on final project, see syllabus.
Schedule:
| Week: |
Homework: |
Material covered: |
| 1 (Jan 22) |
|
Tue: Intro. Slides. Thu: Review of concepts in linear algebra. Gentle introduction to randomized SVD (RSVD). Notes. Additional reading. |
| 2 (Jan 29) |
|
Tue: RSVD. Cost in different environments. Single pass methods. Thu: Fast Johnson-Lindenstrauss transform + RSVD. Theory of RSVD. |
| 3 (Feb 4) |
Tue: Theory of RSVD, continued.
Slides
Thu: Randomized power iteration. Incremental factorizations. |
|
| 4 (Feb 11) |
Homework 1 due on Tuesday. The files hw01p2.m, hw01p3.m, hw01p4.m, hw01p5.m. |
Tue: Interpolatory decompositions and CUR. Thu: No class. |
| 5 (Feb 18) |
|
Tue: Introduction to rank-structured matrices. Hierarchically Off-Diagonal Low Rank (HODLR) matrices. Thu: No class. |
| 6 (Feb 25) |
|
Tue: Inversion and LU factorization of rank-structured matrices. Thu: No class. |
| 7 (March 4) | Homework 2 due on Thursday. |
Tue: The Fast Multipole Method (FFM). Thu: FMM. Notes on FMM. Tutorial code. |
| 8 (March 11) |
|
Tue: FMM. Wed (9-9:50am, RLM 9.166): The potential evaluation map. Slides. Thu: Adaptive FMM. 3D FMM and Helmholtz FMM. Slides. More slides. |
| Spring break |
|
|
| 9 (March 25) | Homework 3 due on Thursday. |
Tue: BIE; video. Thu: BIE; slides. Notes. |
| 10 (April 1) |
|
Tue: BIE. Nystrom discretization; singular kernels. Thu: BIE. Volume and variable coefficient problems. |
| 11 (April 8) |
|
Tue: Solvers for discretized BIEs. Thu: Solvers for discretized BIEs. Slides. Notes. |
| 12 (April 15) | Homework 4 due on Thursday. |
Tue: Solvers for discretized PDEs. Slides. Movie 1; Movie 2. Thu: Solvers for discretized PDEs. |
| 13 (April 22) |
|
Tue: Direct solvers for discretized PDEs. Slides. Thu: Randomized compression of rank-structured matrices. Multigrid. |
| 14 (April 29) |
|
Multigrid. Krylov methods. |
| 15 (May 6) |
Homework 5 due on Thursday. hw5p1.m, hw5p2.m, hw5p4.m. |
Krylov methods and review. |
Resources: