**Instructor:** Anil Damle

**Contact:** damle@cornell.edu

**Office hours:** Mondays and Wednesdays from 2:30 PM to 3:30 PM in 423 Gates Hall

**TA:** David Eriksson

**Contact:** dme65@cornell.edu

**Office hours:** Tuesdays from 9:30 AM - 10:30 AM and Thursdays from 11 AM - 12 PM in 657 Frank H.T. Rhodes Hall, Room 2. (See David's website, linked to above, for directions.)

**Lectures:** Monday, Wednesday, and Friday from 11:15 am till 12:05 pm in Hollister Hall 306

**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 the course management system (CMS). The course also has a discussion website using Piazza.

- October 10 — No class due to instructor travel

Your grade in this course will be determined based on your performance on the homeworks and exams. 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. Homeworks must be typeset and submitted along with the associated code via the CMS.

**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 myself or the TA 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 the CMS.- Midterm exam (available via CMS on October 10, due
**October 15 at 11:59 PM**) - Final exam (available via CMS on December 5, due
**December 12 at 11:30 AM**)

- Midterm exam (available via CMS on October 10, due

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:

- Participation: 5%
- Homeworks: 60%
- Midterm exam: 15%
- Final exam: 20%

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. In contrast, the take home exams are to be completed yourself, and should not be discussed with anyone (besides asking myself or the TA clarifying questions).

Except for the final exam (see above), all work is due at 11:59 pm on the due date. Homeworks and exams must be submitted via the CMS. 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 the CMS, and regrade requests must be submitted within one week.

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.

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.

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. The book by Demmel is also a good reference for a graduate course, and may prove valuable as an additional source.

**Matrix Computations by Golub and Van Loan**

This text covers essentially all of the material discussed in this course and many additional topics we will not have time to discuss—it is the canonical reference text for numerical linear algebra.**Numerical Linear Algebra by Trefethen and Bau**

A good textbook that broadly covers numerical linear algebra at the graduate level. It is well written, certainly more colloquial the Golub and Van Loan, and many find it provides a smoother introduction to the topics we will discuss. However, by construction, it is not as comprehensive as Golub and Van Loan. This book is available online through the library. [Cornell library]**Applied Numerical Linear Algebra by Demmel**

A good textbook that covers numerical linear algebra at the graduate level. 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 two provide coverage of much of the background material for this course.

**Lecture notes by Embree**

A set of lecture notes by Mark Embree for a course in numerical analysis he taught while at Rice. While the content of the notes does not align with this course, they still may be a useful and interesting resource. [online]**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]**CS 6210 in Fall 2016 by Bindel**

The website from the last time the course was taught here at Cornell by David Bindel. The website contains HWs, lecture notes, etc. from that course and may be a useful resource. [online]**Course notes by Saunders**

The lecture notes from a course taught by Michael Saunders (one of the developers of MINRES) on large scale optimization. Specifically, lectures four and five overview much of what we discussed about Krylov methods (and more). For those curious, these notes also provide a brief discussion of Krylov methods for least squares problems and pointers to the relevant literature. [online]

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

8/24 | Introduction | ||

8/27 | Fundamentals | TB: 1-5 | |

8/29 | Fundamentals | TB: 1-5 | |

8/31 | Floating point | TB: 13, GVL: 2.7 | |

9/3 | Labor Day, no class | ||

9/5 | Sensitivity and conditioning | TB: 12, 14, and 15 | |

9/7 | Sensitivity and conditioning | TB: 12, 14, and 15 | Homework 1 due |

9/10 | Sensitivity and conditioning | TB: 12, 14, and 15 | |

9/12 | LU factorizations | TB: 20-22 and GVL: 3.1-3.5 | |

9/14 | LU factorizations | TB: 20-22 and GVL: 3.1-3.5 | |

9/17 | LU factorizations | TB: 20-22 and GVL: 3.1-3.5 | |

9/19 | LU factorizations | TB: 20-22 and GVL: 3.1-3.5 | Homework 2 due |

9/21 | Cholesky factorization | TB: 23 and GVL: 4.2 | |

9/24 | Backward stability and projectors | TB: 6 and 16 | |

9/26 | QR Factorizations | TB: 7-8 and GVL: 5.1-5.2 | |

9/28 | QR Factorizations | TB: 7-8 and GVL: 5.1-5.2 | |

10/1 | QR Factorizations | TB: 7-8 and GVL: 5.1-5.2 | |

10/3 | Least Squares Problems | TB: 11 and 18 | Homework 3 due |

10/5 | Least Squares Problems | TB: 11 and 18 | |

10/8 | Fall break, no class | ||

10/10 | Instructor travel, no class | Midterm exam made available | |

10/12 | Start iterative methods | ||

10/15 | Stationary iterative methods | GVL 11.2 | Midterm exam due |

10/17 | Start Krylov subspace methods | TB: 32, 33, and 36; GVL: 10.1, 10.5, 11.3, and 11.4 | |

10/19 | Lanczos and Arnoldi | TB: 32, 33, and 36; GVL: 10.1, 10.5, 11.3, and 11.4 | |

10/22 | CG and MINRES | TB: 32, 33, and 36; GVL: 10.1, 10.5, 11.3, and 11.4 | |

10/24 | CG and MINRES | TB: 32, 33, and 36; GVL: 10.1, 10.5, 11.3, and 11.4 | |

10/26 | CG and MINRES | TB: 32, 33, and 36; GVL: 10.1, 10.5, 11.3, and 11.4 | |

10/29 | CG and MINRES | TB: 32, 33, and 36; GVL: 10.1, 10.5, 11.3, and 11.4 | |

10/31 | CG and MINRES | TB: 32, 33, and 36; GVL: 10.1, 10.5, 11.3, and 11.4 | Homework 4 due |

11/2 | GMRES | TB: 35 | |

11/5 | Pre-conditioning | TB: 40 | |

11/7 | Eigenvalue Algorithms | TB: 24, 25, and 27 | |

11/9 | Power method, Rayleigh quotient iteration | TB: 24, 25, and 27; GVL: 7.3 and 8.2 | |

11/12 | Power method, Rayleigh quotient iteration | TB: 24, 25, and 27; GVL: 7.3 and 8.2 | |

11/14 | Orthogonal iteration | TB: 24, 25, and 27; GVL: 7.3 and 8.2 | |

11/16 | QR algorithm | TB: 28 and 29; GVL: 7.4, 7.5, and 8.3 | |

11/19 | QR algorithm | TB: 28 and 29; GVL: 7.4, 7.5, and 8.3 | Homework 5 due |

11/21 | Thanksgiving break, no class | ||

11/23 | Thanksgiving break, no class | ||

11/26 | QR algorithm | TB: 28 and 29; GVL: 7.4, 7.5, and 8.3 | |

11/28 | Arnoldi and Lanczos for eigenvectors | ||

11/30 | Arnoldi and Lanczos for eigenvectors | ||

12/3 | Arnoldi and Lanczos for eigenvectors | Homework 6 due | |

12/12 | Final exam | Final exam due at 11:30 AM |