COL 726: Numerical Algorithms
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
Course Description
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.
Evaluation
- Homework assignments: 31% (2 × 5% + 3 × 7%)
- 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:
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.
Lectures
- Monday, 31 Dec: Introduction, conditioning (Heath 1.1, Trefethen & Bau 12)
- 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)
- 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)
- 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
- 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)
- Saturday, 23 Feb: Preconditioning, eigenvalues (TB 40, 24)
- 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)
- 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)
- Monday, 1 Apr: Numerical integration (H 8.1–8.3)
- 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)
- Thursday, 25 Apr: End-of-semester review