CS 6210: Matrix Computations

Cornell University, Fall 2020.
Instruction mode: online, synchronous lectures.
Lectures: 10:20AM–11:10AM MWF, virtual on zoom.

Instructor: Austin Benson, Assistant Professor, Computer Science (arb@cs.cornell.edu).
Office hours: 4:00PM–5:00PM Wednesdays or by appointment, virtual on zoom.

TA: John Paul Ryan, PhD student, Computer Science (jpr269@cornell.edu).
Office hours: 12:00PM–1:00PM Thursdays, virtual on zoom.


Course topics: direct and iterative algorithms for computing solutions to square linear systems, least squares, and eigenvalue problems; matrix factorizations such as QR, LU, and the SVD; stability and error analysis; Krylov subspace methods; special considerations for sparse matrices.

Course administration: Recommended reading material:
  • [GVL] Matrix Computations. G. H. Golub and C. F. Van Loan.
  • [TB] Numerical Linear Algebra. L. N. Trefethen and D. Bau III. Available online from the Cornell skillport (no direct link, need to search).
  • [D] Applied Numerical Linear Algebra. J. W. Demmel. Available online from Cornell's SIAM subscription.
  • [B] Prof. David Bindel's Fall 2019 6210 course notes.
Other useful material:
Homework schedule
Lecture schedule
Note: this schedule is tentative and subject to change.

Week 1
Lecture 1 (W 9/2): introduction, matrix multiplication
Readings: TB 1; D 1.1–1.3. [notes] [video]

Lecture 2 (F 9/4): matrix multiplication on computers, rank, structured matrices
Readings: TB 1; B Aug 30, Sep 04. [notes] [video] [demo]

Week 2
Lecture 3 (M 9/7): norms
Readings: TB 2–3; GVL 2. [notes] [video]

Lecture 4 (W 9/9): the SVD
Readings: TB 4–5; GVL 2.4. [notes] [video] [demo]

Lecture 5 (F 9/11): sensitivity and conditioning
Readings: TB 12; D 1.3. [notes] [video] [demo]

Week 3
Lecture 6 (M 9/14): floating point
Readings: D 1.5; B Sep 13. [notes] [video] [demo]

Lecture 7 (W 9/16): stability
Readings: TB 14–15. [notes] [video]

Lecture 8 (F 9/18): start Gaussian elimination and LU
Readings: TB 20. [notes] [video]

Week 4
Lecture 9 (M 9/21): pivoting and blocking
Readings: TB 21; D 2.4. [notes] [video]

Lecture 10 (W 9/23): error analysis
Readings: TB 22; D 2.4. [notes] [video]

Lecture 11 (F 9/25): sparse direct
Readings: D 2.7.4; B Sep 30. [notes] [video] [demo]

Week 5
Lecture 12 (M 9/28): structured systems and Cholesky
Readings: TB 23; B Sep 27. [notes]

Lecture 13 (W 9/30): least squares
Readings: TB 11. [notes] [video]

Lecture 14 (F 10/2): projectors and Gram-Schmidt
Readings: TB 6–8. [notes] [video]

Week 6
Lecture 15 (M 10/5): Householder and Givens
Readings: TB 10; D 3.4. [notes] [video]

Lecture 16 (W 10/7): least squares sensitivity and conditioning
Readings: D 3.3–3.4; B Oct 9. [notes] [video]

Lecture 17 (F 10/9): stability of Householder; managing ill-conditioning
Readings: D 3.4–3.5; B Oct 16. [notes] [video]

Week 7
Lecture 18 (M 10/12): statistical interpretations
Readings: B Oct 16. [notes] [video] [demo]

Fall break (W 10/14): no lecture

Lecture 19 (F 10/16): start eigenvalue problems
Readings: TB 24–25; GVL 7. [notes] [video]

Week 8
Lecture 20 (M 10/19): power method and inverse iteration, Hessenberg form
Readings: TB 26–27; GVL 7. [notes] [video]

Lecture 21 (W 10/21): subspace / orthogonal iteration and QR iteration
Readings: TB 28; GVL 7. [notes] [video]

Lecture 22 (F 10/23): shifted QR iteration
Readings: TB 28–29; GVL 7. [notes] [video]

Week 9
Lecture 23 (M 10/26): shifted QR iteration, start symmetric eigenvalue problems
Readings: TB 29; GVL 7. [notes] [video]

Lecture 24 (W 10/28): revisit old solvers, plus some new ones
Readings: TB 25–30. [notes] [video]

Lecture 25 (F 10/30): computing the SVD, eigenvalue perturbation theory
Readings: TB 31; D 5.2. [notes] [video] [demo]

Week 10
Lecture 26 (M 11/2): more perturbation theory
Readings: D 4.3, 5.2. [notes] [video]

Lecture 27 (W 11/4): start iterative methods
Readings: D 6.1, 6.4. [notes] [video] [demo]

Lecture 28 (F 11/6): stationary iterative methods
Readings: D 6.5. [notes] [video]

Week 11
No class M 11/9 (travel)

Lecture 29 (W 11/11): Krylov subspaces intro, Arnoldi, Lanczos
Readings: TB 32, 33, 36. [notes] [video]

Lecture 30 (F 11/13): CG through Lanczos
Readings: TB 36, 38. [notes] [video]

Week 12
No classes (semi-final study days).

Week 13
No classes (semi-finals + Thanksgiving break).

Week 14
Lecture 31 (M 11/30): CG error analysis
Readings: TB 38. [notes] [video]

Lecture 32 (W 12/2): CG as a gradient method
Readings: TB 38; GVL 11.3. [notes] [video]

Lecture 33 (F 12/4): MINRES
Readings: GVL 11.4; Michael Saunder's notes. [notes] [video]

Week 15
Lecture 34 (M 12/7): GMRES and preconditioning
Readings: TB 35, 40. [notes] [video] [demo]

Lecture 35 (W 12/9): LSQR and LSMR
Readings: TB 39; Michael Saunder's notes. [notes] [video]

Lecture 36 (F 12/11): Iterative solvers for eigenproblems
Readings: TB 34. [notes] [video]

Week 16
Lecture 37 (M 12/14): Low-rank tensor decompositions
Readings: GVL 12.5. [notes] [video] [demo]

Lecture 38 (W 12/16): review / wrap-up / future
Readings: GVL; TB; D; B. [notes] [video]

Coursework will be managed through, and assignments submitted on, CMS. The required coursework consists of three components:
  • Homeworks (70%).
    There will be seven homeworks that will have theoretical and/or coding components. Each is worth 10% of your grade.
  • Final exam (25%).
    There will be a take-home final exam, with a format similar to previous offerings of 6210. This is worth 25% of your grade. There is no midterm or semi-final.
  • Participation (5%).
    Showing up to class, asking questions, coming to office hours, providing feedback, Piazza participation, and other engagement with the course will count towards participation. Participation is worth 5% of your grade. Showing up to at least 80% of the synchronous virtual lectures is sufficient for a full participation score.