Instructor: Anil Damle

Contact: damle@cornell.edu

Office hours: Monday 3 - 4 pm and Wednesday 10:45 - 11:45 am in 423 Gates Hall.

TA: Qinru Shi

Contact: qs63@cornell.edu

Office hours: Thursday 3 - 4 pm on Zoom (see Canvas for Zoom link)

Lectures: Tuesday and Thursday from 1:00 pm to 2:15 pm in Upson Hall 216.

Course overview: Stable and efficient algorithms for linear equations, least squares, and eigenvalue problems. Both direct and iterative methods are considered. Specific examples include QR and LU factorizations, Krylov subspace methods, the QR algorithm, and stationary iterative methods.

Course websites: Homeworks and exams will be turned in using Gradescope, the course also has a discussion website using Ed, and recorded lectures are available via Canvas.

Homework and exams


Your grade in this course will be determined based on your performance on the homework and exams. Please also read through the given references for each lecture.

Grading

Your grade on individual assignments will be determined based on both the correctness of your solutions and the clarity of their exposition (e.g., plots should be readable and clearly articulate what you are asked to show). Your final grade in the course will be computed based on the homework and exams in the following manner:

References


Books

We will not be explicitly following any single textbook in this course. Nevertheless, the books by Golub and Van Loan, and Trefethen and Bau collectively cover the material for the course and are recommended. Most suggested readings are assigned out of these two texts. Three additional texts are provided that complement these texts and are useful for further study (or to gain another perspective).

Other

In addition to the above textbooks there are numerous other online resources that you may find useful listed below. In particular, the first provides coverage of much of the background material for this course.

Schedule


A tentative schedule follows, and includes the topics we will be covering, relevant reference material, and assignment information. It is quite possible the specific topics covered on a given day will change slightly. This is particularly true for the lectures in the latter part of the course, and this schedule will be updated as necessary.

Date Topic References Notes/assignments
1/25 Introduction The definition of numerical analysis by Nick Trefethen
1/27 Fundamentals TB: 1-5, GVL: 2.7 On the early history of the singular value decomposition by G. W. Stewart
2/1 Floating point plus sensitivity and conditioning TB: 12 and 13
2/3 Accuracy and stability TB: 14 and 15
2/8 Triangular factorizations (Pivoted LU) TB: 20, 21, 22, and 23; GVL 3.1 - 3.5 Homework 1 due
2/10 Triangular factorizations (Pivoted LU) TB: 20, 21, 22, and 23; GVL 3.1 - 3.5
2/15 Triangular factorizations (Cholesky) and projection matrices TB: 23 and 6, and GVL: 4.2
2/17 Least Squares and QR factorizations TB: 6, 7, and 11
2/22 Algorithms for QR factorizations TB: 8, 10, and 16; GVL 5.1, 5.2, and 5.3
2/24 Algorithms for QR factorizations TB: 8, 10, and 16; GVL 5.1, 5.2, and 5.3 Homework 2 due
3/1 February break, no class
3/3 Least squares sensitivity and rank-deficient problems TB 19 and GVL 5.5
3/8 Stationary iterative methods GVL 11.2 Homework 3 due
3/10 Krylov methods: Arnoldi and Lanczos TB 33 and 36, and GVL 10.1 and 10.5.1 Midterm released
3/15 Krylov methods: CG and MINRES TB 35 and 38, and GVL 11.3 and 11.4
3/17 Krylov methods: convergence analysis and GMRES TB 35 and 38, and GVL 11.3 and 11.4 Midterm due
3/22 Krylov methods: Least squares and preconditioning TB 40 and GVL 11.4.2
3/24 Krylov methods demo
3/29 Eigenvalue/vector problems: subspace distance and sensitivity TB 24 and 25, and GVL 7.1, 7.2, and 8.1
3/31 Eigenvalue/vector problems: power iteration and orthogonal iteration TB 27 and GVL 7.3 and 8.2 Homework 4 due (tentative)
4/12 Reduction to Hessenberg form and QR iteration TB 26, 28, and 29, and GVL 7.4, 7.5, and 8.3
4/14 QR iteration (with shifts) TB 26, 28, and 29, and GVL 7.4, 7.5, and 8.3
4/19 Divide and conquer Demmel 5.3.3
4/21 Computing the SVD TB 31 and GVL 8.6
4/26 Lanczos for eigenvalues/vectors GVL 10.1 and 10.3
4/28 Lanczos for singular values/vectors TB 36 and GVL 10.4 Homework 5 due on 4/29
5/3 Arnoldi for eigenvalues TB 34 and GVL 10.5
5/5 FEAST and intro to randomized NLA HW 6 due on 5/9
5/10 randomized NLA and rank-revealing algorithms

Course policies


Participation

You are encouraged to actively participate in class. This can take the form of asking questions in class, responding to questions to the class, and actively asking/answering questions on the online discussion board. We will also be soliciting feedback mid-semester to hopefully improve the course.

Collaboration policy

You may discuss the homework freely with other students, but please refrain from looking at code or writeups by others. You must ultimately implement your own code and write up your own solution. In contrast, the take home exams are to be completed yourself, and should not be discussed with anyone.

Late work and grading

Except for the final exam, all work is due at 11:59 pm on the due date. Homework and exams must be submitted via Gradescope. For each homework assignment you are allowed up to two "slip days". You may not use slip days for the take-home exams.

Grades will be posted to Gradescope, and regrade requests must be submitted within one week.

Prerequisites

This course will require a mathematical background, particularly in linear algebra though we will also use some calculus and approximation theory. There will also be implementation based questions on the homeworks and exams, and therefore some programming knowledge is required as well.

Academic integrity

The Cornell Code of Academic Integrity applies to this course.

Accommodations

In compliance with the Cornell University policy and equal access laws, I am available to discuss appropriate academic accommodations that may be required for student with disabilities. Requests for academic accommodations are to be made during the first three weeks of the semester, except for unusual circumstances, so arrangements can be made. Students are encouraged to register with Student Disability Services to verify their eligibility for appropriate accommodations.

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. [Statement reproduced with permission from Dan Grossman.]

COVID-19 considerations

We understand that the ongoing global health pandemic impacts all of you in varied and profound ways. Therefore, flexibility is important as we continue to navigate the current state of affairs. While many aspects of this course are built with flexibility in mind, if situations arise that may require additional accommodations please reach out to the instructor to discuss potential arrangements.

Mental health resources

Cornell University provides a comprehensive set of mental health resources.