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

CLASS ZOOM LINKS HERE

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: Recommended reading material:
  • [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.
Other useful material:
Homeworks
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.