Course overview: 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.
Instructor: Anil Damle
Contact: damle@cornell.edu
Office hours: Monday from 10 AM - 11 AM and Wednesday from 11 AM - 12 PM in 423 Gates Hall, or by appointment.
TA: John Ryan
Contact: jpr269@cornell.edu
Office hours: Tuesday 1 PM - 2 PM in Rhodes 400 and Tuesday 3:30 PM - 4:30 PM in Rhodes 408
TA: Junteng Jia
Contact: jj585@cornell.edu
Office hours: Thursday 4 PM - 5 PM in Rhodes 412
TA: Ilya Amburg
Contact: ia244@cornell.edu
Office hours: See Piazza
Undergraduate TA: Sooyoun Oh
Contact: so339@cornell.edu
Office hours: Wednesday from 1 PM - 2 PM in 572 Rhodes Hall and Friday from 1 PM to 2 PM in 584 Rhodes Hall
Lectures: Monday, Wednesday, and Friday from 2:30 pm till 3:20 pm in Gates Hall G01
Course websites: Homework, projects, and exams will be turned in using the course management system (CMS). The course also has a discussion website using Piazza.
Your grade in this course is comprised of three components: homework, projects, and exams. Please also read through the given references in concert with the lectures.
There will be five homework assignments throughout the course, typically made available roughly two weeks before the due date. They will include a mix of mathematical questions and implementation of algorithms. Implementation may be done in MATLAB, Julia, or Python. Homeworks should be typed and submitted via the CMS.
There will be two open ended assignments, which we will refer to as projects. These assignments will present problems (with some guidance towards a solution) that you should be able to complete using the tools and techniques covered in the course. Implementation may be done in MATLAB, Julia, or Python. Projects (both code and a typed writeup) should be submitted via the CMS.
There will be two take-home exams in this course, a midterm and a final. These exams are open book and note. However, you may not discuss the exam with anyone (besides asking the instructor clarifying questions), and are expected to complete them on your own. Implementation may be done in MATLAB, Julia, or Python. Your exam solutions and code should be typed and submitted via the CMS
Your final grade in the course will be computed based on the homework, projects, exams, and course 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.
You may discuss the homework and projects 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 (besides asking the instructor clarifying questions).
Except for the final exam, all work is due at 11:59 pm on the due date. Homework and projects should be submitted via the CMS. For each assignment you are allowed up to two "slip days". However, over the course of the semester you may only use a total of eight slip days. You may not use slip days for the take-home exams.
Grades will be posted to the CMS, and regrade requests must be submitted within one week.
Linear algebra at the level of MATH 2210 or 2940 or equivalent and a CS 1 course in any language. We will assume you remember your calculus and can pick up MATLAB, Julia, or Python. Recommended but not essential: one additional mathematics course numbered 3000 or above. This course can be taken before or after CS 4210/MATH 4250.
The Cornell Code of Academic Integrity applies to this course.
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.
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.
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/23 | Introduction | ||
| 1/25 | Linear algebra background | AG: 4 (and above references) | |
| 1/28 | Linear algebra background | AG: 4 (and above references) | |
| 1/30 | Numerical algorithms and conditioning | AG: 1 | |
| 2/1 | Linear algebra background | AG: 4 (and above references) | |
| 2/4 | Floating point | AG: 1,2 | |
| 2/6 | Accuracy and stability | AG: 1,2 | Homework 1 due |
| 2/8 | LU and pivoting | AG: 5.2 and 5.3 | |
| 2/11 | LU, pivoting, and Cholesky | AG: 5.2 and 5.3 | |
| 2/13 | Error analysis of direct methods | AG: 5.4 and 5.8 | |
| 2/15 | Sparse matrices | AG: 5.5, 5.6, and 5.7 | |
| 2/18 | Intro to least squares problems | AG: 5.6, 5.7, and 6.1 | |
| 2/20 | Least squares and QR | AG: 6.2 and 6.3 | Homework 2 due |
| 2/22 | QR factorizations | AG: 6.2 and 6.3 | |
| 2/27 | QR factorizations via Householder | AG: 6.2 and 6.3 | |
| 3/1 | Ill-posedness and regularization | ||
| 3/4 | Intro to eigenvalue problems | AG: 8.1 | |
| 3/6 | Power and subspace iteration | AG: 8.1 | Project 1 due |
| 3/8 | QR iteration | AG: 8.3 | Midterm posted |
| 3/11 | Upper Hessenberg and tridiagonal forms | AG: 8.3 | |
| 3/13 | Introduction to optimization | ||
| 3/15 | Nonlinear equations in 1D | Midterm 1 due | |
| 3/18 | Stationary iterative methods | AG: 7.1, 7.2, and 7.3 | |
| 3/20 | Krylov subspaces and CG | AG: 7.4 and 7.5 | |
| 3/22 | Preconditioning | AG: 7.4 and 7.5 | |
| 3/25 | Nonlinear equations and optimization | AG: 9.1 and 9.2 | |
| 3/27 | Nonlinear equations and optimization | AG: 9.1 and 9.2 | |
| 3/29 | Newtons method | AG: 9.1 and 9.2 | Homework 3 due |
| 4/8 | Newtons method | AG: 9.1 and 9.2 | |
| 4/10 | Quasi-Newton and other iterations | AG: 9.1 and 9.2 | |
| 4/12 | Gradient methods | AG: 9.1 and 9.2 | |
| 4/15 | Line search | AG: 9.1 and 9.2 | |
| 4/17 | BFGS | AG: 9.1 and 9.2 | Homework 4 due |
| 4/19 | BFGS and practical tips | AG: 9.1 and 9.2 | |
| 4/22 | Modified Newton and trust region | AG: 9.1 and 9.2 | |
| 4/24 | Constraints | AG: 9.3 | |
| 4/26 | Constraints | AG: 9.3 | Project 2 due |
| 4/29 | Constraints | AG: 9.3 | |
| 5/1 | Iteratively reweighted least squares | ||
| 5/3 | Flex time | ||
| 5/6 | Review | Homework 5 due | |
| 5/8 | Final exam posted at 4:30 PM | Final exam posted at 4:30 PM | |
| 5/15 | Final exam due at 4:30 PM | Final exam due at 4:30 PM |