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.

CLASS ZOOM LINKS HERE

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.

Resources

Course administration:

• CMS for managing course work.
• Piazza for asking and answering questions.
• Jupyter notebooks and data for class demos.

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:

• Accuracy and Stability of Numerical Algorithms. N. J. Higham. Available online from Cornell's SIAM subscription.
• Prof. Michael Saunder's course notes (Lecture 1 for background; Lectures 4+5 for iterative methods).
• Iterative Methods for Solving Linear Systems. A. Greenbaum. Available online from Cornell's SIAM subscription.
• Iterative Methods for Linear Systems. Y. Saad. Available online from Prof. Saad's web site.
• Prof. Anil Damle's Fall 2018 offering of 6210.
• Julia language documentation for linear algebra, sparse arrays, and iterative solvers.

Homework schedule

• Homework 1 due Fri Sep 18 at 10:19am ET (before class) [source]
• Homework 2 due Fri Oct 2 at 10:19am ET (before class) [source]
• Homework 3 due Fri Oct 16 at 10:19am ET (before class) [source]
• Homework 4 due Fri Oct 30 at 10:19am ET (before class) [source]
• Homework 5 due Fri Nov 13 at 10:19am ET (before class) [source]
• Homework 6 due Fri Dec 4 at 10:19am ET (before class) [source]
• Homework 7 due Wed Dec 16 at 10:19am ET (before class) [source]

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

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.