**Instructor:**

Rahul Narain

narain@cse.iitd.ac.in

**Class times:**

Slot M (Mon, Thu 5–6:30pm)

Bharti IIA-201

**Office hours:**

Wed, Thu 10:30–11:30am

Bharti IIA-517

**Links:**

Moodle

Piazza

Gradescope

**Content (tentative):** Conditioning and stability, floating-point arithmetic. *Numerical linear algebra*: Vector and matrix norms, singular value decomposition, QR factorization, LU and Cholesky factorizations, conjugate gradient method, eigenvalue algorithms. *Beyond linear algebra:* root finding, interpolation, numerical integration and differentiation, unconstrained and constrained optimization.

**Relevant textbooks:**

- Heath,
*Scientific Computing: An Introductory Survey* - Trefethen and Bau,
*Numerical Linear Algebra* - Boyd and Vandenberghe,
*Convex Optimization*

**Prerequisites:** Introductory courses in linear algebra, calculus, and programming.

- Homework assignments: 31% (2 × 5% + 3 × 7%)
- Homework 1: 10–17 Jan
- Homework 2: 24–31 Jan
- Homework 3 (
`makeNetwork.py`

): 22 Feb–1 Mar - Homework 4 (
`fcontour.py`

): 14–22 Mar - Homework 5 (
`hw5starter.py`

): 12–22 Apr

- Minor I: 20%
- Minor II: 20%
- Major: 29%

Students are expected to use Python 3 with Numpy and Scipy for the programming component of the homework. If you are not familiar with these, please go through one of the following tutorials:

- Getting started with Python for science from the Scipy Lecture Notes
- Python Numpy Tutorial from the Stanford CS231n notes

**Late policy:** Homework assignments are due at midnight on the due date. A 20% penalty will be applied to homework submitted up to 24 hours late, a 40% penalty between 24 and 48 hours late, and zero points after more than 48 hours.

**Collaboration policy:** All work you submit for the homework assignments must be your own. You are welcome to discuss the assignment problems in general with others, but you must work out and write your own solutions: any in-person or online discussion should stop before you start discussing or designing a specific solution. Note this means means not only writing the final answer or program, but also key preliminary and intermediate steps such as solution design, debugging, etc. Copying others’ solutions or letting another person copy your solutions is a serious violation, and can result in failing the course and additional disciplinary action.

If you used external resources such as Wikipedia for help in any of your homework solutions, you must cite them explicitly in your report, and write the solution completely in your own words (not copied from the external resource) to demonstrate that you understand it yourself. The same applies for any programming component: the code should also be written from scratch.

If you have any questions about what is and is not allowable in this class, please contact the course instructor.

- Monday, 31 Dec: Introduction, conditioning (Heath 1.1, Trefethen & Bau 12)
- Practice exercises: Heath review questions 1.14, 1.15, 1.18–1.20
- Further reading: Goldberg, “What every computer scientist should know about floating-point arithmetic”, 1991

- Thursday, 3 Jan: Floating-point arithmetic, accuracy and stability (Trefethen & Bau 13, 14, 15)
- Practice exercises: Heath review questions 1.24, 1.36, 1.45, 1.47, 1.50, Trefethen & Bau exercises 13.2, 13.3, 14.2, 15.1
- Floating-point error demo

- Monday, 7 Jan: Review of linear algebra (Trefethen & Bau 1, 2)
- Practice exercises: Trefethen & Bau 1.1, 1.4, 2.1, 2.2, 2.6

- Thursday, 10 Jan: Norms (TB 3)
- Practice exercises: TB 3.1, 3.2 (assume all eigenvalues are real), 3.3, 3.5

- Thursday, 17 Jan: The singular value decomposition (TB 4, 5)
- Practice exercises: TB 4.1, 4.2, 4.4, 5.2
- Further Reading: Ranade, “Some uses of spectral methods”

- Monday, 21 Jan: Projectors and QR factorization (TB 6, 7)
- Practice exercises: TB 6.1, 6.2, 6.5, 7.1–7.5

- Thursday, 24 Jan: Gram-Schmidt and Householder methods (TB 8, 9, 10)
- Practice exercises: TB 8.2 (in Python), 8.3, 9.3, 10.1–10.4
- Further Reading: Moler, “Compare Gram-Schmidt and Householder Orthogonalization Algorithms”, 2016

- Monday, 28 Jan: Solving linear and least-squares problems (TB 16, 11)
- Practice exercises: TB 16.1, 11.1, 11.3 (use
`scipy.linalg.solve`

for Matlab’s`\`

) - Further reading: TB 17 (“Stability of Back Substitution”)
- QR backward stability demo

- Practice exercises: TB 16.1, 11.1, 11.3 (use
- Thursday, 31 Jan: Conditioning of least-squares problems (TB 18, 19)
- Practice exercises: TB 18.1, 18.2, 18.4

- Monday, 11 Feb: LU factorization (TB 20, 21, 22)
- Practice exercises: TB 20.1, 20.2, 20.4, 20.5, 21.2, 21.3, 21.6

- Thursday, 14 Feb: Cholesky factorization, iterative methods (TB 23, 32)
- Practice exercises: TB 23.1, 23.2, 32.1

- Monday, 18 Feb: Stationary iterative methods, Arnoldi and GMRES (Heath 11.5.1–4, TB 33, 35)
- Practice exercises: Heath exercises (not review questions) 11.6, 11.7, TB 33.2, 35.4, 35.5

- Thursday, 21 Feb: Conjugate gradients (TB 38)
- Practice exercises: TB 35.3, 35.6, 38.2, 38.4
- Further reading: Shewchuk, “An Introduction to the Conjugate Gradient Method Without the Agonizing Pain”, 1994

- Saturday, 23 Feb: Preconditioning, eigenvalues (TB 40, 24)
- Practice exercises: TB 24.1, 24.2, 24.3 (use
`scipy.linalg.expm`

for the matrix exponential and`scipy.linalg.norm(…, 2)`

for the 2-norm), 24.4 - Further reading: TB 39 (“Biorthogonalization Methods”); Nachtigal et al., “How Fast are Nonsymmetric Matrix Iterations?”, 1992

- Practice exercises: TB 24.1, 24.2, 24.3 (use
- Monday, 25 Feb: Eigenvalue algorithms (TB 25, 26, 27)
- Practice exercises: TB 25.1, 25.2, 26.1, 27.1, 27.3–6

- Thursday, 28 Feb: The QR algorithm, conditioning of eigenvalues (TB 28, Heath 4.3)
- Practice exercises: TB 28.1–4
- Further reading: Page et al., “The PageRank Citation Ranking: Bringing Order to the Web”, 1999

- Monday, 11 Mar: Nonlinear equations (Heath 5.1–5.5.3)
- Practice exercises: Heath review questions 5.12, 5.16, Heath exercises 5.3, 5.6, 5.12

- Thursday, 14 Mar: Nonlinear systems, interpolation (H 5.6, 7.1–7.3.1)
- Practice exercises: H review questions 5.23, 5.24, exercises 5.8, 5.9, 5.11, 5.13

- Saturday, 16 Mar: More about polynomial interpolation (H 7.3)
- Practice exercises: H review questions 7.15, exercises 7.1, 7.3, 7.6, 7.7, 7.11

- Monday, 18 Mar: Piecewise polynomial interpolation (H 7.4–7.4.2)
- Practice exercises: H review questions 7.28, exercises 7.15
- Further reading: Fritsch and Carlson, “Monotone Piecewise Cubic Interpolation”, 1980

- Monday, 1 Apr: Numerical integration (H 8.1–8.3)
- Practice exercises: H exercises 8.1, 8.2(a), 8.3–5, 8.7, 8.11
- Further reading: Trefethen, “Six Myths of Polynomial Interpolation and Quadrature”, 2011

- Thursday, 4 Apr: Numerical integration and differentiation (H 8.4.3–4, 8.6–7)
- Practice exercises: H review questions 8.32, 8.33, exercises 8.13–15

- Monday, 8 Apr: Convex sets and functions (Boyd and Vandenberghe 2.1–3, 3.1–2)
- Practice exercises: Boyd and Vandenberghe 2.1, 2.4, 2.6, 2.12, 3.4, 3.6, 3.7, 3.20(a), 3.21(a), 3.30

- Thursday, 11 Apr: Unconstrained optimization (BV 4.1–2, 9.1–4)
- Practice exercises: BV 4.1, 9.1, 9.6, 9.8

- Monday, 15 Apr: Newton’s method, constrained optimization (BV 9.5, 4.3–4, 5.1)
- Practice exercises: BV 9.9, 9.10, 4.8, 4.11 (see “Piecewise linear minimization” in BV Sec. 4.3.1)

- Thursday, 18 Apr: Duality, equality constrained optimization (BV 5.2, 5.5, 10.1–2)
- Practice exercises: BV 5.1, 5.14, 5.24, 5.26, 10.1, 10.2, 10.5

- Monday, 22 Apr: Inequality constrained optimization (BV 10.3, 11.1–4)
- Practice exercises: BV 10.8, 11.1, 11.2, 11.7
- Further reading: Gould, “Penalty and augmented Lagrangian methods for equality constrained optimization”, 2006

- Thursday, 25 Apr: End-of-semester review