Numerical Linear Algebra, August-December 2018

Credits 9 credits
When F slot (Tuesday,Wednesday, Thursday, Friday)
Where Humanities and Sciences Block, Room 266

Instructor

Sivaram Ambikasaran,

Office hours: 2PM-4PM, Mondays, HSB 241C

Teaching Assistant

Vaishnavi Gujjula, ma16d301@smail.iitm.ac.in
Office hours: 2PM-4PM, Wednesdays

Flyer The course flyer can be found here

Fill in the details here to subscribe for the course

Assignments

Total of \(15\) assignments due on Wednesdays before 5 PM.
Late assignments will be marked zero.
There will be both written and computational part in the assignments.
We will be using AutoGradr to evaluate the computational part of the assignment. Register as a student on AutoGradr.
Students are strongly encouraged to typeset their solutions using \(\LaTeX/\TeX\) (10% bonus points for submitting in \(\LaTeX\)/\(\TeX\)).
Students need to drop their assignments (both written and code) via the dropbox link. Each assignment has its own dropbox link. You need to have your roll number as the folder name (all characters in small case), compress it (either zip or rar or tar or any compression format), when you upload it.
Any copying on assignments will give you a zero on the assignment.
We will be using JPlag to detect similarities among multiple sets of source code files.
The grader will expect you to express your ideas clearly, legibly, and completely, often requiring complete English sentences rather than merely just a long string of equations or unconnected mathematical expressions. This means you could lose points for poorly written proofs or answers. Clear exposition is a crucial ingredient of technical communication. Clarity of thought and presentation is more important in mathematics & sciences than any other field. The only way to master exposition is by repeated practicing.
Assignment grades can be found here.

Lectures

Lecture Summary

Calendar

First Class will be on August 1, 2018, Wednesday. Below is a tentative calendar, which will be updated as we make progress in the course.

Week	Tuesday	Wednesday	Thursday	Friday	Assignment

Jul 30- Aug 3	No class	Motivation	Chapter 1; BD	Chapter 1; BD	Assign-1: Due Aug 8 Drop Assignment; Solution
Aug 6-10	Chapter 1,2; BD	Holiday	Chapter 2; BD	No class	Assign-2: Due Aug 15 Drop Assignment; Solution
Aug 13-17	No class	Class on Monday; Chapter 3, BD	Chapter 3, BD	Gaussian elimination and the need for pivoting	Assign-3: Due Aug 22 Drop Assignment; Solution
Aug 20-24	No Class	Holiday	Stability	LU factorization	Assign-4: Due Aug 29 Drop Assignment; Solution
Aug 27-31	No Class	LU factorization and asymptotically optimal algorithms	Partial Pivoted LU	Quiz-I, August \(31\) Quiz-I solutions; Performance summary	Assign-5: Due Sept 5 Drop Assignment; Solution
Sep 3-7	No class	No class	No class	Complete pivoting, cost of pivoting, Cholesky	Assign-6: Due Sept 12 Drop Assignment; Solution
Sep 10-14	No class	Cholesky, Least squares	Holiday	No class	Assign-7: Due Sept 26 Drop Assignment; Solution
Sep 17-21	Least squares, Least norm (Monday)			Holiday	Assign-8: Due Sept 30 Drop Assignment; Solution
Sep 24-28
Oct 1-5					Assign-9: Due October 21 Drop Assignment
Oct 8-12				Quiz-II, October \(12\), Quiz-II solutions
Oct 15-19				Holiday
Oct 22-26
Oct 29-Nov 2
Nov 5-9				Last day of class	Assign-10: Due November 14Drop Assignment
Nov 26-30	EndSem, November \(27\)

Grading

Evaluation	Assignments	Quiz-I	Quiz-II	Final Exam
Points	30	15	15	40

Detailed Syllabus

Matrix and vector norms, floating points arithmetic, forward and backward stability of algorithms, conditioning of a problem, perturbation analysis, algorithmic complexity, Solving linear systems, Gaussian elimination, LU factorization, Pivoting, Cholesky decomposition, Iterative refinement, QR factorization, Gram-Schmidt orthogonalization, Projections, Householder reflectors, Givens rotation, Singular Value Decomposition, Least squares and least norm solution of linear systems, pseudoinverse, normal equations, Eigenvalue problems, Gershgorin theorem, Similarity transform, Eigenvalue & eigenvector computations and sensitivity, Power method, Schur decomposition, Jordan canonical form, QR iteration with & without shifts, Hessenberg transformation, Rayleigh quotient, Symmetric eigenvalue problem, Jacobi method, Divide and Conquer, Computing the Singular Value Decomposition, Golub-Kahan-Reinsch algorithm, Chan SVD algorithm, Rank and matrix approximations, image compression using SVD, Generalized SVD, Generalized and Quadratic eigenvalue problems, generalized Schur decomposition (QZ decomposition), Iterative methods for large linear systems: Jacobi, Gauss-Seidel and SOR, convergence of iterative algorithms, Krylov subspace methods: Lanczos, Arnoldi, MINRES, GMRES, Conjugate Gradient and QMR, Pre-conditioners, Approximating eigenvalues and eigenvectors, Structured matrix computations, Designing matrix algorithms on modern computer architectures

Textbooks

We will be drawing material from all three books. Notes will be posted as and when required.

Other references

Linear Algebra by Gilbert Strang: His course and book can be considered to be a pre-requisite for this course.

Exams

Practice Final-I Practice Final-II

Exam	Date
Quiz-I	August \(31\), Friday
Quiz-II	October \(12\), Friday
End Term	November \(27\), Tuesday