TA:
Ziheng Zhang, POB 4.140.
Email: ziheng@utexas.edu
Office hours: Tuesdays 13:00 - 14:00, Thursdays 14:00 - 15:00.
Meeting times:
Tuesdays and Thursdays, 9:30 - 10:45. ECJ 1.308
Website:
http://users.oden.utexas.edu/~pgm/Teaching/2026_NLA/
Syllabus:
pdf
Description:
Accurate and efficient algorithms for solving linear algebraic problems form a cornerstone of scientific and engineering computations. They play an essential role in machine learning, data analysis, and computational statistics. In these areas, tasks such as solving linear systems, computing eigenvectors and eigenvalues of large matrices, solving linear regression problems, low-rank approximation, etc., often form the core of large scale computations. The class will describe efficient techniques for solving problems such as these. Both the theoretical foundations of the methods, and practical considerations for how to implement the methods efficiently, will be covered. The course will include both classical deterministic algorithms and more recent randomized techniques for large-scale linear algebra.
The course will also discuss essential concepts of numerical analysis such as backwards and forwards error analysis, stability of numerical methods, and floating point arithmetic. Particular attention will be paid to modern mixed precision computing, including how computations carried out partly in lower precision can nevertheless produce highly accurate results.
Examination:
25% for homeworks, 51% for the section exams (17% for each of the three), 24% for the final exam. See syllabus for details.
Late policy: The first time you hand in a homework late, you will get 70% credit provided that you hand your work in within 5 days of the due date. Any subsequent late homeworks will receive no credit.
Schedule: All future times are tentative!
| Week: |
Homework: |
Material covered: |
| 1 (Aug 24) |
Tue: Review of basic concepts in linear algebra; matrix operations and fundamental subspaces (ch 1). Thu: Orthonormal matrices; vector and operator norms (ch 2-3). |
|
| 2 (Aug 31) |
Tue: SVD: geometry, full and reduced factorizations (ch 4). Thu: More on the SVD: fundamental subspaces, norms, and low rank approximation (ch 5). The matlab code used in class. |
|
| 3 (Sep 7) | Homework 1 due on Friday Sep 11. |
Tue: Projections and QR factorization (ch 6-7). Thu: Gram-Schmidt QR (ch 8). Chapter 9 is part of prereqs. Please review as required. Code used in class. Also this. |
| 4 (Sep 14) |
Tue: Householder QR (ch 10). Thu: Least squares problems (ch 11). The matlab code used in class. |
|
| 5 (Sep 21) | Homework 2 due on Friday Sep 25. |
Tue: Least squares problems and applications (ch 11). Section exam 1 in class on Thursday Sep 24. |
| 6 (Sep 28) |
Tue: Conditioning and condition numbers (ch 12). Thu: Floating point arithmetic (ch 13). |
|
| 7 (Oct 5) | Homework 3 due on Friday Oct 9. |
Tue: Forward and backward error; stability of numerical algorithms (ch 14-15). Thu: Mixed precision computing and iterative refinement. The matlab code used in class. |
| 8 (Oct 12) |
Tue: Stability of Householder QR (ch 16-17); conditioning and stability of least squares problems (ch 18-19). The matlab code used in class. Section exam 2 in class on Thursday Oct 15. |
|
| 9 (Oct 19) | Homework 4 due on Friday Oct 23. |
Tue: Gaussian elimination and LU factorization (ch 20-21). Thu: Pivoting and stability of Gaussian elimination (ch 21-22). Codes: LU, LU and pivoting, conditioning of LU. |
| 10 (Oct 26) |
Tue: Cholesky factorization (ch 23). Matlab demo. Thu: Computing eigenvalues and eigenvectors: basic ideas, power iteration, inverse iteration, and Rayleigh quotient iteration (ch 24-27). |
|
| 11 (Nov 2) | Homework 5 due on Friday Nov 6. |
Tue: Dense eigenvalue problems: Hessenberg/tridiagonal reduction and subspace iteration (ch 26-28). Thu: Dense eigenvalue problems: the QR algorithm and related methods (ch 28-30). |
| 12 (Nov 9) |
Tue: Krylov methods: Arnoldi, Ritz values, and GMRES (ch 32-35). Thu: Krylov methods: Lanczos and conjugate gradients (ch 36, 38). |
|
| 13 (Nov 16) |
Tue: Krylov methods: preconditioning and related iterative techniques (ch 39-40). If time permits, a brief introduction to sparse direct solvers. Video lecture on conjugate gradients. (Voluntary!) Video lecture on Krylov for non-normal matrices. (Voluntary!) Video lecture on preconditioners. (Voluntary!) Section exam 3 in class on Thursday Nov 19. |
|
| (Nov 23) | Thanksgiving break (Nov 23-28). No classes. | |
| 14 (Nov 30) | Homework 6 due on Monday Nov 30. |
Tue: Randomized methods in numerical linear algebra: sketching, low-rank approximation, least squares problems. Thu: Review. |
| (Dec 14) | Final exam on Monday Dec 14, 8:00am - 10:00am. |
Resources: