Instructor: Anil Damle

Contact: damle@cornell.edu

Office hours: Monday 3 - 4 and Wednesday 2 - 3 in Gates 423

TA: Mariia Soroka

Contact: ms3663@cornell.edu

Office hours: Tuesday 5:30 - 6:30 in Rhodes 402 and Thursday 3:30 - 4:30 in Rhodes 404

TA: Yi Xu

Contact: yx622@cornell.edu

Office hours: Thursday 9 - 10 in Rhodes 400 and Friday 2 - 3 in Rhodes 404

Lectures: Monday, Wednesday, and Friday from 11:15 to 12:05 am in Gates Hall G01.

Course description: Introduction to the fundamentals of numerical linear algebra: direct and iterative methods for linear systems, eigenvalue problems, singular value decomposition. In the second half of the course, the above are used to build iterative methods for nonlinear systems and for multivariate optimization. Strong emphasis is placed on understanding the advantages, disadvantages, and limits of applicability for all the covered techniques. Computer programming is required to test the theoretical concepts throughout the course.

Course websites: Homework and exams will be turned in using Gradescope and the course also has a discussion website using Ed.

Credit hours and grading schemes: This course is 4 credit hours and can be taken for a letter grade, S/U, or audit (auditing is only available to graduate students).

Prerequisites: This course requires sufficient mathematical maturity, particularly in linear algebra (e.g., MATH 2210 or MATH 2940) and multivariable calculus (e.g., MATH 2220 or MATH 1920), though we will also use some approximation theory. As we will also write proofs, it is also helpful to have add at least one additional 3000+ math course or relevant CS course (e.g., CS 2800 or CS 3220). There will also be implementation based questions on the homework and exams, and therefore some programming knowledge is required as well.

Homework and exams


For undergraduates (i.e., those enrolled in CS 4220 or Math 4260), your grade in this course will be determined based on your performance on the homework, projects, and exams. For graduate students (i.e., those enrolled in CS 5223) there will be an additional paper review that consitutes part of your grade. 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).

For CS 4220 and Math 4260 your final grade in the course will be computed based on the homework and exams in the following manner:

For CS 5223 your final grade in the course will be computed based on the homework and exams in the following manner:

References


Books

The text by Ascher and Greif listed below serves as the primary reference text for the material covered in the class. Importantly, it is available for free online through Cornell's SIAM subscription. I have also included some additional references that may help prove to be useful resources.

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/22 Introduction The definition of numerical analysis by Nick Trefethen
1/24 Linear algebra background AG: 4 (and above references)
1/26 Linear algebra background AG: 4 (and above references)
1/29 Numerical algorithms and error AG: 1
1/31 Sensitivity and conditioning AG: 1,2
2/2 Floating point AG: 2
2/5 Floating point AG: 2 Homework 1 due
2/7 LU, pivoting AG: 5.1, 5.2, and 5.3
2/9 LU, pivoting, Cholesky AG: 5.1, 5.2, and 5.3
2/12 LU with complete pivoting and Choleksy AG: 5.3 and 5.5
2/14 Sparse matrices AG: 5.6 and 5.7
2/16 Least squares problems and QR factorizations AG 6.1 and 6.2
2/19 QR factorization AG 6.3 Homework 2 due
2/21 QR factorization AG 6.3
2/23 Ill-posedness and regularization AG: 8.2
2/26 No class, February break
2/28 Intro to Eigenvalue problems AG: 8.1 and Notes on perturbation theory
3/1 Power and subspace iteration AG: 8.1
3/4 Orthogonal iteration AG: 8.3
3/6 QR algorithm AG: 8.3
3/8 QR algorithm and the SVD AG: 8.3 Homework 3 due
3/11 Classical iterations AG: 7.2 and 7.3 Project 1 due
3/13 Krylov subspace methods AG: 7.4 and 7.5 Midterm posted
3/15 Krylov subspace methods: convergence AG: 7.4 and 7.5
3/18 Krylov subspace methods: preconditioning AG: 7.4 and 7.5
3/20 Nonlinear equations and optimization AG: 9.1 Midterm due
3/22 Intro to optimization AG: 9.2
3/25 Search direction methods: gradient descent and newton AG: 9.2
3/27 Line search AG: 9.2 Paper review proposal due 3/28
3/29 Quasi-Newton Methods AG: 9.2
4/1 No class, Spring break
4/3 No class, Spring break
4/5 No class, Spring break
4/8 BFGS AG: 9.2
4/10 BFGS and practical tips AG: 9.2
4/12 Gauss-Newton AG: 9.2 Homework 4 due
4/15 Iteratively reweighted least squares AG: 9.2
4/17 Constraints AG: 9.3
4/19 Constraints AG: 9.3
4/22 Constraints AG: 9.3
4/24 Constraints
4/26 Stochastic optimization Section 5 of Optimization for Modern Data Analysis by Recht and Wright Homework 5 due
4/29 Randomized NLA SIAM Review paper by Halko, Martinsson, and Tropp
5/1 Randomized NLA SIAM Review paper by Halko, Martinsson, and Tropp Project 2 due
5/3 Randomized NLA SIAM Review paper by Halko, Martinsson, and Tropp
5/6 Review Homework 6 and paper review due (5/7)
5/16 Final exam due May 16 at 12:00 pm

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. Similarly, you may discuss the projects with other groups, but each group must ultimately produce their own code and report. In contrast, the take home exams are to be completed yourself, and should not be discussed with anyone. The paper review is also an individual assignment, though you are free to discuss the paper with others as long as you produce your own review.

Late work and grading

Except for the final exam, all work is due at 11:59 pm on the due date. Homework, projects, and exams must be submitted via Gradescope. For each homework assignment, project, and the paper review 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.

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

Mental health resources

Cornell University provides a comprehensive set of mental health resources.