COL726: Numerical Algorithms

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:

Textbooks:

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)
  1. Mon, 8 Feb: Floating-point arithmetic, accuracy and stability (Trefethen & Bau 13–15)
  2. Thu, 11 Feb: Review of linear algebra (TB 1)
  1. Mon, 15 Feb: Orthogonality, vector norms (TB 2, 3.“Vector Norms”)
  2. Thu, 18 Feb: Matrix norms, SVD (TB 3, 4)
  1. Mon, 22 Feb: Projectors, QR factorization (TB 6, 7, 8 up to “Modified Gram-Schmidt Algorithm”)
  2. Thu, 25 Feb: Householder triangularization (TB 8 from “Operation Count” onwards, 9, 10)
  1. Mon, 1 Mar: Solving linear and least-squares problems (TB 16, 11, 18 up to “Sensitivity of x to Perturbations in b”)
  2. Thu, 4 Mar: LU factorization (TB 20, 21, 22)
  1. Mon, 8 Mar: Cholesky factorization (TB 23)
  2. Thu, 11 Mar: Iterative methods, Arnoldi, GMRES (TB 32, 33, 35 up to “Convergence of GMRES”)
  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”)
  2. Thu, 25 Mar: Eigenvalue algorithms (TB 26 from “Operation Count” onwards, 27, 28)
  1. Thu, 1 Apr: Conditioning of eigenvalues, nonlinear equations (Heath 4.3, 5.1–5.5.2)
  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)
  1. Mon, 12 Apr: Convex functions, optimization problems (BV 3.1–2, 4.1–4.1.2, 4.2–4.2.2)
  2. Thu, 15 Apr: Optimality conditions, descent methods (BV 4.1.3, 4.2.3–4, 9.1–4)
  1. Mon, 19 Apr: Newton and quasi-Newton methods (BV 9.5, H 6.5.4–5)
  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)
  1. Mon, 26 Apr: Constrained optimality conditions, equality constrained optimization (BV 5.2.3–4, 5.5, 10.1–2)
  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.