**Content:** 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. *Nonlinear problems:* root finding, ~~interpolation, numerical integration and differentiation,~~ unconstrained and constrained optimization.

**Objectives:** At the end of the course, students will be able to:

- Analyze the conditioning of numerical problems and the stability of numerical algorithms
- State and derive the stability properties, computational complexity, and applicability criteria of standard numerical algorithms
- Identify the numerical algorithms best suited for given problems
- Solve complex problems by designing and implementing appropriate combinations of numerical algorithms

**Textbooks:**

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

**Prerequisites:** COL106 or equivalent. Overlaps with MTL704. Familiarity with linear algebra and calculus is assumed.

- Thu, 4 Feb: Introduction, conditioning (Heath 1.1–1.2, Trefethen & Bau 12)
- Practice exercises: Heath exercises 1.1–1.6

- Mon, 8 Feb: Floating-point arithmetic, accuracy and stability (Trefethen & Bau 13–15)
- Practice exercises: Trefethen & Bau exercises 13.*, 14.*, 15.1

- Thu, 11 Feb: Review of linear algebra (TB 1)
- Practice exercises: TB 1.*

- Mon, 15 Feb: Orthogonality, vector norms (TB 2, 3.“Vector Norms”)
- Practice exercises: TB 2.*, 3.1, 3.3(a,b)

- Thu, 18 Feb: Matrix norms, SVD (TB 3, 4)
- Practice exercises: TB 3.2, 3.3(c,d), 3.4–6, 4.* (use
`numpy.linalg.svd`

for 4.3) - 5.5. Sunday, 21 Feb: More about SVD (TB 5)
- Further reading: Ranade, “Some uses of spectral methods”
- Practice exercises: TB 5.*

- Practice exercises: TB 3.2, 3.3(c,d), 3.4–6, 4.* (use

- Mon, 22 Feb: Projectors, QR factorization (TB 6, 7, 8 up to “Modified Gram-Schmidt Algorithm”)
- Practice exercises: TB 6.*, 7.*, 8.1–2 (all programming exercises should be done in Python)

- Thu, 25 Feb: Householder triangularization (TB 8 from “Operation Count” onwards, 9, 10)
- Practice exercises: TB 8.3, 9.* (use Matplotlib for plotting), 10.*

- Mon, 1 Mar: Solving linear and least-squares problems (TB 16, 11, 18 up to “Sensitivity of
*x*to Perturbations in*b*”)- Practice exercises: TB 16.*, 11.*, 18.1–2, 18.4

- Thu, 4 Mar: LU factorization (TB 20, 21, 22)
- Further reading: Higham, “What Is the Growth Factor for Gaussian Elimination?”, 2020; Spielman and Teng, “Smoothed Analysis: An Attempt to Explain the Behavior of Algorithms in Practice”, 2009
- Practice exercises: TB 20.*, 21.*, 22.1–3

- Mon, 8 Mar: Cholesky factorization (TB 23)
- Practice exercises: TB 23.* (in 23.3, think about how you could implement a function
`solve(A,b)`

that performs similarly to Matlab’s`A\b`

)

- Practice exercises: TB 23.* (in 23.3, think about how you could implement a function
- Thu, 11 Mar: Iterative methods, Arnoldi, GMRES (TB 32, 33, 35 up to “Convergence of GMRES”)
- Practice exercises: TB 32.*, 33.1–2, 35.4–5

- Saturday, 20 Mar: GMRES, conjugate gradient method (TB 35 from “Polynomials Small on the Spectrum” onwards, 38)
- Further reading: Shewchuk, “An Introduction to the Conjugate Gradient Method Without the Agonizing Pain”, 1994
- Practice exercises: TB 35.1–3, 35.6, 38.*

- Mon, 22 Mar: Eigenvalues (TB 24, 25, 26 up to “A Good Idea”)
- Practice exercises: TB 24.* (use
`scipy.linalg.expm`

for the matrix exponential), 25.*

- Practice exercises: TB 24.* (use
- Thu, 25 Mar: Eigenvalue algorithms (TB 26 from “Operation Count” onwards, 27, 28)
- Practice exercises: TB 26.* (use
`matplotlib.pyplot.contour`

), 27.* (look up*convex hull*on p. 24 of Boyd & Vandenberghe), 28.*

- Practice exercises: TB 26.* (use

- Thu, 1 Apr: Conditioning of eigenvalues, nonlinear equations (Heath 4.3, 5.1–5.5.2)
- Practice exercises: Heath review questions 5.5, 5.9–14

- Mon, 5 Apr: Nonlinear systems of equations (H 5.5.3–4, 5.6)
- Further reading: Grinshpan, “The order of convergence for the secant method”
- Practice exercises: Heath review questions 5.15–17, 5.23–24, exercises 5.1–6, 5.8–14, computer problems 5.27–29

- Thu, 8 Apr: Optimization, convex sets (Boyd & Vandenberghe 1, 2.1–3, 2.5)
- Practice exercises: Boyd & Vandenberghe exercises 2.1–16, 2.20–27

- Mon, 12 Apr: Convex functions, optimization problems (BV 3.1–2, 4.1–4.1.2, 4.2–4.2.2)
- Practice exercises: BV 3.(1–12,15–22,28–31)

- Thu, 15 Apr: Optimality criteria, descent methods (BV 4.1.3, 4.2.3–4, 9.1–4)
- Practice exercises: BV 4.(1–3,5), 9.(1–3,5–6,8)

- Mon, 19 Apr: Newton and quasi-Newton methods (BV 9.5, H 6.5.4–5)
- Thu, 22 Apr: Constrained optimization and Lagrange duality (BV 5.1–2, 5.3–4)

- Mon, 26 Apr: Equality constrained optimization (BV 10.1–3)
- Thu, 29 Apr: Interior point methods (BV 11.1–4, 11.7)

- Mon, 3 May: Other constrained optimization algorithms (H 6.7.1–2)

- Homework assignments: 40% (dates for future assignments are
*tentative*and subject to change)- Assignment 1: 15 Feb – 1 Mar
- Assignment 2: 27 Feb – 13 Mar
- Assignment 3: 20 Mar – 3 Apr
- Assignment 4: 2 Apr – 16 Apr
- Assignment 5: 16 Apr – 30 Apr

- Minor: 25%
- Major: 35%

Students should use Python 3 with Numpy/Scipy for the programming component of the homework. If you do not have prior experience with these libraries, please go through one of the following tutorials to familiarize yourself:

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

**Grading:** Following institute policy, a minimum of 80% marks are required for an A grade, and minimum 30% marks for D.

**Late policy:** Homework assignments are due at midnight on the due date. You are allowed a total of 5 late days across all the assignments. Any assignment submitted late after the total allowed late days have been used will not be graded.

**Audit policy:** A minimum of 40% marks is required for audit pass.

**Attendance policy:** ~~Attendance lower than 50% may result in a one-grade penalty (e.g. A to A–, or A– to B).~~ There are no attendance requirements.

**Collaboration policy:** Adapted from Dan Weld’s guidelines, via Mausam:

Collaboration is a very good thing. On the other hand, cheating is considered a very serious offense. Please don’t do it! Concern about cheating creates an unpleasant environment for everyone. If you cheat, you get a zero in the assignment, and additionally you risk losing your position as a student in the department and the institute. The department’s policy on cheating is to report any cases to the disciplinary committee. What follows afterwards is not fun.

So how do you draw the line between collaboration and cheating? Here’s a reasonable set of ground rules. Failure to understand and follow these rules will constitute cheating, and will be dealt with as per institute guidelines.

The Kyunki Saas Bhi Kabhi Bahu Thi Rule:This rule says that you are free to meet with fellow students(s) and discuss assignments with them. Writing on a board or shared piece of paper is acceptable during the meeting; however, you should not take any written (electronic or otherwise) record away from the meeting. This applies when the assignment is supposed to be an individual effort or whenever two teams discuss common problems they are each encountering (inter-group collaboration). After the meeting, engage in a half hour of mind-numbing activity (like watching an episode ofKyunki Saas Bhi Kabhi Bahu Thi), before starting to work on the assignment. This will assure that you are able to reconstruct what you learned from the meeting, by yourself, using your own brain.

The Right to Information Rule:To assure that all collaboration is on the level, you must always write the name(s) of your collaborators on your assignment. This also applies when two groups collaborate.