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

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.

**Homework:**There will be several homework assignments (tentatively six) 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. Homework solutions must be typeset and submitted along with the associated code via Gradescope.

- Homework 1 [Latex file]
- Homework 2 [Latex file] [Data file]
- Homework 3 [Latex file]
- Homework 4 [Latex file]
- Homework 5 [Latex file]
- Homework 6 [Latex file]

**Projects:**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, Python, or Julia. Projects (both code and a typeset report) will be submitted via Gradescope. Projects may be completed in groups of up to three students.

**Paper review:**Graduate students will also have to complete a comprehensive paper review as part of this course. Your review must discuss what problem the paper is trying to solve or what question is being asked, the technical details of the solution/answer, how it fits in with related work, and a critique of the paper (e.g., did it satisfactorily address the key issues, were the numerical experiments convincing, are assumptions needed for theoretical claims reasonable, etc.). While your review is for a single paper, you may have to peruse some related papers to understand the area. Similarly, you could include short numerical experiments of your own, if applicable, as part of your critique.

The first deliverable will be around the midpoint of the semester and include the title of the paper you will review along with a brief justification for why you chose it. The paper can certainly be something related to your research, but it should be one you haven't gone through in full detail before. I have deliberately left the choice of paper wide open. It should be at least somewhat related to the topics of the course, and I am happy to provide suggestions if you are interested. Your review will be due at the end of the semester. Both the proposal and review must be typeset and will be submitted via Gradescope.

- Paper proposal: March 28, 2024
- Paper review: May 3, 2024

**Exams:**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 me clarifying questions) and are expected to complete them on your own. We reserve the right to use software systems (

*e.g.,*MOSS) to check for solution similarity. Implementation may be done in MATLAB, Julia, or Python. Your exam solutions must be typeset and submitted along with the associated code via Gradescope.- Midterm exam: Due March 20 at 11:59 pm (released on March 13)
- Final exam: Due May 16 at 12:00 pm (released on May 9)

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:

- Participation: 5%
- Homework: 30%
- Projects: 20%
- Midterm exam: 20%
- Final exam: 25%

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

- Participation: 5%
- Homework: 25%
- Projects: 20%
- Paper review: 5%
- Midterm exam: 20%
- Final exam: 25%

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 First Course in Numerical Methods by Ascher and Greif**

This book serves as the primary reference for this course and covers a broad range of topics in numerical analysis. Sections are abbreviated as AG in the references below. [SIAM online]**Numerical Linear Algebra by Trefethen and Bau**

A good textbook that broadly covers numerical linear algebra, though at a graduate level. Nevertheless, it is well written, and may prove useful as a secondary source of information for some of the material. This book is also available online through the library. [Cornell library]**Applied Numerical Linear Algebra by Demmel**

A good textbook that covers numerical linear algebra, though at a graduate level and in significantly more technical detail than this course. Nevertheless, it may prove useful as a secondary source of information for some of the material, or as a vehicle for further study. This book is also available online through through Cornell's SIAM subscription. [SIAM online]

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.

**Linear algebra course by Strang**

Portions of this course will utilize your knowledge of linear algebra. If you feel you need additional preparation, or would like to revisit the topic, you may find Gilbert Strangs linear algebra course quite useful. [MIT Open Courseware]**Prior years CS 4220 website**

Much of this course, at least topically, will match what was taught over the last could of years. Therefore, you may find the notes and other resources from prior years class useful. [CS 4220 — Spring 2023]**Julia**

If you need resources for the Julia language, the documentation and various resources (under the learning link) are available on the Julia website. If consulting the documentation, please make sure the documentation you are consulting is for the version matching what you are running. [Julia webpage]**MATLAB**

One useful resource for MATLAB is the book "Insight through Computing: A MATLAB Introduction to Computational Science and Engineering" by Van Loan and Fan. It is available for free online through Cornell's SIAM subscription. [SIAM online] You may also find the online documentation helpful. [MATLAB documentation]**LaTeX**

Further information about LaTeX, including how to obtain/install it, may be found at the projects homepage. In addition, there is a WikiBook you may find useful if you are looking to learn LaTeX. Lastly, you may find the online platform Overleaf (loosely speaking, a Google Docs for LaTeX) useful and they have their own tutorial.

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

4/1 | No class, Spring break | ||

4/3 | No class, Spring break | ||

4/5 | No class, Spring break | ||

4/8 | BFGS | ||

4/10 | BFGS and practical tips | ||

4/12 | Modified Newton and trust region | Homework 4 due | |

4/15 | Constraints | ||

4/17 | Constraints | ||

4/19 | Constraints | ||

4/22 | Iteratively reweighted least squares | ||

4/24 | Stochastic optimization | Homework 5 due | |

4/26 | Randomized NLA | ||

4/29 | Randomized NLA | ||

5/1 | Flex time | Project 2 due | |

5/3 | Flex time | Paper review due | |

5/6 | Review | Homework 6 due | |

TBA (5/11 - 5/18) | Final Exam due |

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

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.

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.

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

Cornell University provides a comprehensive set of mental health resources.