#### CS 4220/Math 4260: Numerical Analysis: Linear and Nonlinear Problems

Cornell University, Spring 2021.Instruction mode: online, synchronous lectures.

Lectures: 3:45PM–4:35PM (ET) M/W/F, virtual on zoom.

Instructor: Austin Benson, Assistant Professor, Computer Science (arb@cs.cornell.edu).

Office hours: 2:00PM–3:00PM (ET) Wednesdays or by appointment, virtual on zoom.

TA: Michael Xu, PhD student, Center for Applied Mathematics (xx294@cornell.edu).

Office hours: 4:00PM–5:00PM (ET) Thursdays, virtual on zoom.

Course support staff: Jordan Staiti, Computer Science (jas2262@cornell.edu).

Course topics: direct and iterative algorithms for solving linear systems; least squares; eigenvalue problems; matrix factorizations such as QR, LU, and the SVD; numerical optimization basics such as gradient descent and (quasi-)Newton.

Feedback: We welcome feedback on the class during the semester. You should always feel free to email the professor and TA. If you want to provide anonymous (to Prof. Benson and TA Michael) feedback, please send it via email to Jordan, and the information will be communicated.

##### Inclusiveness

You should expect and demand to be treated by your classmates and the course staff with respect. You belong here, and we are here to help you learn and enjoy this course. If any incident occurs that challenges this commitment to a supportive and inclusive environment, please let the instructors know so that the issue can be addressed. We are personally committed to this, and subscribe to the Computer Science Departmentâ€™s Values of Inclusion.(This statement is based on a similar one from Dan Grossman at Washington.)

##### Resources

Course administration:- CMS for managing coursework.
- VOD channel for lecture recordings.
- Ed Discussion for asking and answering questions.
- Jupyter notebooks and data for class demos.

- [B] Prof. David Bindel's CS4220 course notes from Spring 2020.
- [AG] A First Course in Numerical Methods. U. Ascher and C. Greif. Available online.
- [TB] Numerical Linear Algebra. L. N. Trefethen and D. Bau III. Available online (no direct link, need to search).
- [NW] Numerical Optimization. J. Nocedal and S. J. Wright. Available online.
- [BV] Convex Optimization. S. Boyd and L. Vandenberghe. Available online.

- Julia programming language documentation for linear algebra, sparse arrays, and iterative solvers.
- Latex typesetting wikibook: Basics and Mathematics.

##### Homeworks

- Homework 1 due Fri Feb 26 at 3:44pm ET (before class) [source]
- Homework 2 due Fri Mar 12 at 3:44pm ET (before class would normally start) [source]
- Homework 3 due Fri Mar 26 at 3:44pm ET (before class) [source]
- Homework 4 due Fri Apr 16 at 3:44pm ET (before class) [source]
- Homework 5 due Fri Apr 30 at 3:44pm ET (before class) [source]
- Homework 6 due Fri May 14 at 3:44pm ET (before class) [source]

##### Lectures

Note: this schedule is tentative and subject to change.**Week 1**

**Lecture 1 (M 02/08): course intro and basic linear algebra review**

Readings: B Jan 22, Jan 24, Jan 27. [notes] [video]

**Lecture 2 (W 02/10): multiplying matrices and vectors on computers; structured matrices**

Readings: B Jan 22, Jan 24, Jan 27. [notes] [video] [demo]

**Lecture 3 (F 02/12): norms**

Readings: B Jan 22, Jan 24, Jan 27. [notes] [video]

**Week 2**

**Lecture 4 (M 02/15): the SVD**

Readings: TB 4–5. [notes] [video] [demo]

**Lecture 5 (W 02/17): sensitivity and conditioning**

Readings: B Jan 29. [notes] [video]

**Lecture 6 (F 02/19): floating point and backward stability**

Readings: B Jan 31. [notes] [video] [demo]

**Week 3**

**Lecture 7 (M 02/22): Gaussian elimination and LU**

Readings: B Feb 5. [notes] [video]

**Lecture 8 (W 02/24): pivoted LU**

Readings: B Feb 10, 12; TB 21. [notes] [video]

**Lecture 9 (F 02/26): LU error analysis**(Michael Xu lecturing)

Readings: B Feb 10, 12. [notes] [video]

**Week 4**

**Lecture 10 (M 03/01): SPD and sparse LU**

Readings: B Feb 14. [notes] [video]

**Lecture 11 (W 03/03): introduction to least squares**

Readings: B Feb 17. [notes] [video]

**Lecture 12 (F 03/05): computing QR factorizations**

Readings: B Feb 19. [notes] [video] [demo]

**Week 5**

**Lecture 13 (M 03/08): computing QR factorizations and stability; least squares sensitivity and conditioning**

Readings: B Feb 17, 19, 21. [notes] [video]

**No lecture W 03/10 (wellness day)**

**No lecture F 03/12 (instructor "travel")**

**Week 6**

**Lecture 14 (M 03/15): least squares and regularization**

Readings: B Feb 21. [notes] [video]

**Lecture 15 (W 03/17): introduction to eigenvalue problems**

Readings: B Feb 28. [notes] [video]

**Lecture 16 (F 03/19): power iteration and subspace iteration**

Readings: B Mar 3. [notes] [video]

**Week 7**

**Lecture 17 (M 03/22): QR iteration**

Readings: B Mar 4. [notes] [video] [demo]

**Lecture 18 (W 03/24): practicalities and other considerations**

Readings: B Mar 4. [notes] [video]

**Lecture 19 (F 03/26): introduction to numerical optimization in one dimension**

Readings: B Mar 9, Apr 6. [notes] [video]

**Week 8**

**Lecture 20 (M 03/29): 1-D optimization and root finding**

Readings: B Mar 9, 11. [notes] [video] [demo]

**Lecture 21 (W 03/31): introduction to multivariate numerical optimization**

Readings: B Apr 13. [notes] [video]

**Lecture 22 (F 04/02): Newton's method in many dimensions**

Readings: B Apr 15. [notes]

**Week 8**

**Lecture 23 (M 04/05): quasi-Newton methods**

Readings: B Apr 20. [notes] [video]

**Lecture 24 (W 04/07): gradient methods**

Readings: B Apr 22. [notes] [video]

**Lecture 25 (F 04/09): line search**

Readings: B Apr 24. [notes] [video] [demo]

**Week 9**

**Lecture 26 (M 04/12): splitting methods for linear systems**

Readings: B Apr 8. [notes] [video]

**Lecture 27 (W 04/14): Krylov methods for linear systems**

Readings: B Apr 10. [notes] [video]

**Lecture 28 (F 04/16): more iterative solvers**

Readings: B Apr 10. [notes] [video] [demo]

**Week 10**

**Lecture 29 (M 04/19): Gauss-Newton; trust-region methods**

Readings: B Apr 27. [notes] [video]

**Lecture 30 (W 04/21): start constrained optimization**

Readings: B May 1. [notes] [video]

**No lecture F 04/23 (wellness day)**

**Week 11**

**No lecture M 04/26 (wellness day)**

**Lecture 31 (W 04/28): equality constraints**

Readings: B May 4. [notes] [video]

**Lecture 32 (F 04/30): inequality constraints**

Readings: B May 6. [notes] [video]

**Week 12**

**Lecture 33 (M 05/03): introduction to convex optimization**

Readings: BV Chapters 1, 2, 3, 4. [notes] [video]

**Lecture 34 (W 05/05): examples of convex optimization problems**

Readings: BV Chapters 6, 7, 8. [notes]

**Lecture 35 (F 05/07): finish lasso; start stochastic gradient descent**

[notes] [video]

**Week 13**

**Lecture 36 (M 05/10): stochastic gradient descent**

[notes] [video]

**Lecture 37 (W 05/12): recap / end / review**

[notes] [video]

**Lecture 38 (F 05/14): AMA / review**

##### Coursework

Coursework will be managed through, and assignments submitted on, CMS. The required coursework consists of four components:Homeworks (48%).

There will be six homeworks that will have theoretical and/or coding components. Each is worth 8% of your grade. Submissions need to be typeset with latex.Midterm exam (16%).

There will be a take-home midterm, released on March 29 and due April 5 before class starts. The format is just like the homework, except that you have to work on the problems on your own.Final exam (32%).

There will be a take-home final, released on May 18 and due May 25. The format is the same as the midterm.Participation (4%).

Showing up to virtual lectures, asking questions, coming to office hours, providing feedback, Ed Discussion involvement, and other engagement with the course will count towards participation.