Numerical Linear Algebra, August-December 2016

When Tuesday and Thursdays morning from 8:30 AM to 10:00 AM
Where Department of Computational & Data Sciences, SERC building, Room 102, Seminar Hall

Instructor

Sivaram Ambikasaran,

Office: Department of Computational & Data Sciences, SERC building, Room 205.
Office hours: Tuesday 3:00 PM-5:00 PM or by appointment.

Teaching Assistant

Navchetan Awasthi,

Office: Department of Computational & Data Sciences, SERC building, Room 208.
Office hours: Tuesday 2:00 PM-3:00 PM.

Flyer

Fill in the details here to subscribe for the course

Syllabus

Matrix and vector norms, floating points arithmetic, forward and backward stability of algorithms, conditioning of a problem, perturbation analysis, algorithmic efficiency, Structured matrices, 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, Rank and matrix approximations, image compression using SVD, 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, 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.

Textbooks

Numerical Linear Algebra and Applications, 2nd Edition, by Biswa Nath Datta
Numerical Linear Algebra, by Lloyd N. Trefethen & David Bau III

We will attempt to cover the book by Biswa Nath Datta. Some material (especially the later part of the course) will be drawn from Trefethen & Bau as well. Notes will be posted as and when required.

Other useful texts to possess:

Applied Numerical Linear Algebra, by James W. Demmel
Matrix Computation, by Gene H. Golub & Charles F. Van Loan
Functions of Matrices: Theory and Computation, by Nicholas Higham
Accuracy and Stability of Numerical Algorithms, by Nicholas Higham

Other references

Linear Algebra by Gilbert Strang. The course site has lecture notes, assignments and videos. In addition, his book will be a good place to start reading linear algebra.

Grading

Evaluation	Homework	Quiz	Midterm	Final Exam
Points	30	10	25	35

Homework

There will be a total of 15 homework due roughly weekly. Homework will be posted on this website and will be due on Wednesday before 5 PM. Late homework will not be accepted. The homework will consist of 3-4 written questions and couple of MATLAB/C++ exercises. Students are strongly encouraged to typeset their solutions using LaTeX/TeX (10% bonus points for submitting in LaTeX/TeX). To save trees, the students need to send their homework through email to

with the subject reading NLA_2016_HW_#_firstname, where # needs to be replaced with the homework number (between 1 and 15) and firstname is to be replaced with your first name in lower case. Details on how to submit the computing part of the homework will be elaborated in the homework itself. No collaboration is allowed for homework.

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 mathematical 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.

\(\LaTeX\)

To use \(\LaTeX\), try any of the following online LaTeX compilers.

https://www.sharelatex.com/
https://www.overleaf.com/

Computational requirement

Each homework will have couple of computational exercises. Students must be comfortable with programming and are expected to have working knowledge in C++ & MATLAB. If not, they should be able to learn and immediately pick it up. Depending on the comfort level of students with coding, I may reduce/remove the coding part from the subsequent assignments or might have them as extra credit/bonus.

C++ compilers

For C++ compilers, try any of the following (there any many other options if you google for "online compiler"). Pick your favorite one.

http://www.tutorialspoint.com/compile_cpp11_online.php
https://www.codechef.com/ide

Quiz

There will be roughly a dozen short (3-5 minutes) surprise quiz in class, which will used for marking attendance.

Exams

Midterm : October 4th, Tuesday in class.

Final exam : December 5th, Monday, from 3:00 PM to 5:00 PM.

There will be no make up exams. All exams will be closed book, closed notes. No internet/calculator allowed.

Calendar

Below is a tentative calendar, which will be updated as we make progress in the course. The chapters mentioned below are from the book by Biswa Nath Datta (unless and otherwise stated explicitly).

Week	Tuesday	Thursday	Homework

Aug 8-12	Motivation & Chapter 1	Chapter 2
Aug 15-19	Chapter 2, Chapter 3	No Class	HW1_P7.cpp HW 1: Due Aug 17 HW1soln
Aug 22-26	Chapter 3; Catastrophic cancellation in computing recurrences Example 1; Example 2	Chapter 4; Disasters due to round-off and numerical errors; Solving 1D Poisson equation; Pivoting in Linear Systems	HW 2: Due Aug 26 HW2soln
Aug 29-Sep 2	Chapter 4	Chapter 5; Backward stability of triangular systems; Backward stability of inner & outer product;	HW 3: Due Aug 31 HW3soln
Sep 5-9	Chapter 5; Slides	Chapter 6	HW 4: Due Sep 7 HW4soln
Sep 12-16	Holiday (Bakrid)	Chapter 6	HW 5: Due Sep 14 HW5soln
Sep 19-23	Least squares	No Class	HW 6: Due Sep 21 HW6soln
Sep 26-30	Least squares, Least norm	QR decompostion; Gram-Schmidt	HW 7/Practice Midterm: Due Sep 28 HW7soln
Oct 3-7	Midterm	QR decompostion; Householder & Givens	Midterm solutions: Oct 4 Midterm statistics
Oct 10-14	Holiday (Vijayadashami)	No Class	HW8: Due Oct 13
Oct 17-21	Eigen values/vectors; Schur decomposition	Eigen decompostion	HW 9: Due Oct 21
Oct 24-28	Eigen decompostion	No Class	HW 10: Due Oct 26
Oct 31-Nov 4	Holiday	Computing the SVD	HW 11: Due Nov 2
Nov 7-11	Iterative methods - Jacobi	No Class	HW 12: Due Nov 9
Nov 14-18	Gauss-Siedel, SOR; Steepest Descent	Conjugate gradient	HW 13: Due Nov 22
Nov 21-25	Conjugate gradient	GMRES, Preconditioning	HW 14: Due Nov 25
Nov 28-Dec 2			HW 15: Due Dec 3
Dec 5-9	Final exam		Practice final