Semester II, 2020-21

Course Description

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.

Lectures

1. Thu, 4 Feb: Introduction, conditioning (Heath 1.1–1.2, Trefethen & Bau 12)
• Practice exercises: Heath exercises 1.1–1.6
1. Mon, 8 Feb: Floating-point arithmetic, accuracy and stability (Trefethen & Bau 13–15)
• Practice exercises: Trefethen & Bau exercises 13.*, 14.*, 15.1
2. Thu, 11 Feb: Review of linear algebra (TB 1)
• Practice exercises: TB 1.*
1. Mon, 15 Feb: Orthogonality, vector norms (TB 2, 3.“Vector Norms”)
• Practice exercises: TB 2.*, 3.1, 3.3(a,b)
2. 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)
• Practice exercises: TB 5.*
1. 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)
2. Thu, 25 Feb: Householder triangularization (TB 8 from “Operation Count” onwards, 9, 10)
• Practice exercises: TB 8.3, 9.* (use Matplotlib for plotting), 10.*
1. 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
2. Thu, 4 Mar: LU factorization (TB 20, 21, 22)
1. 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`)
2. 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
1. Saturday, 20 Mar: GMRES, conjugate gradient method (TB 35 from “Polynomials Small on the Spectrum” onwards, 38)
1. 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.*
2. 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.*
1. 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
1. Mon, 5 Apr: Nonlinear systems of equations (H 5.5.3–4, 5.6)
2. 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
1. 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)
2. Thu, 15 Apr: Optimality conditions, 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)
1. Mon, 19 Apr: Newton and quasi-Newton methods (BV 9.5, H 6.5.4–5)
• Practice exercises: BV 9.(4,10,11,24,25)
2. Thu, 22 Apr: Constrained optimization, Lagrange duality (BV 4.3–4.3.1, 4.4–4.3.1, 5.1–5.1.5, 5.2–5.2.2)
• Further reading: Heath 6.6 (“Nonlinear Least Squares”)
• Practice exercises: BV 4.(8–12,21), 5.(1,2,4,5,7,8,11–14)
1. Mon, 26 Apr: Constrained optimality conditions, equality constrained optimization (BV 5.2.3–4, 5.5, 10.1–2)
• Practice exercises: BV 5.(21,23,24,26–28,31), 10.(2,5)
2. Thu, 29 Apr: Inequality constrained optimization (BV 10.3–10.3.2, 11.1–4)
1. Mon, 3 May: Other constrained optimization algorithms (H 6.7.1–2)

Evaluation

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:

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 6 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. As per Institute guidelines, the minimum requirement for audit pass is 30% marks.

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