#### 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.

##### Resources

Course administration:- CMS for managing course work.
- Piazza for asking and answering questions.
- Jupyter notebooks and data for class demos.

- [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.

- 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.