Numerical Linear Algebra, AugustDecember 2018
Credits 9 credits
When F slot (Tuesday,Wednesday, Thursday, Friday)
Where Humanities and Sciences Block, Room 264
Instructor
Sivaram Ambikasaran,
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, GramSchmidt 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, GolubKahanReinsch 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, GaussSeidel and SOR, convergence of iterative algorithms, Krylov subspace methods: Lanczos, Arnoldi, MINRES, GMRES, Conjugate Gradient and QMR, Preconditioners, Approximating eigenvalues and eigenvectors, Structured matrix computations, Designing matrix algorithms on modern computer architectures
Textbooks
 Numerical Linear Algebra and Applications, 2nd Edition, by Biswa Nath Datta from now on abbreviated as BD
 Applied Numerical Linear Algebra, by James W. Demmel from now on abbreviated as JD
 Numerical Linear Algebra, by Lloyd N. Trefethen & David Bau III from now on abbreviated as TD
We will be drawing material from all three books. Notes will be posted as and when required.
Other useful texts to read:
 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
Grading
Evaluation 
Homework 
QuizI 
QuizII 
Final Exam 
Points 
30 
20 
20 
30 
Homework
There will be a total of \(15\) homework due roughly weekly. Homework will be posted on this website and will be due on Monday before 5 PM. Late homework will not be accepted. The homework will consist of both written questions and 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 2018_NLA_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.
Grading: 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.
\(\LaTeX\)
To use \(\LaTeX\), try any of the following online LaTeX compilers.
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.
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.
Exams
Exam 
Date 
QuizI 
August \(31\), Friday 
QuizII 
October \(12\), Friday 
End Term 
November \(27\), Tuesday 
All exams will be closed book, closed notes, closed calculator, closed computer, closed tablet, closed internet. Did I miss any thing else? Please have an open mind though.
Calendar
Below is a tentative calendar, which will be updated as we make progress in the course.
Week 
Tuesday 
Wednesday 
Thursday 
Friday 
Homework 





Jul 30 Aug 3 

Motivation & Chapter 1 from BD 


HW1: Due Aug 6 
Aug 610 




HW2: Due Aug 13 
Aug 1317 
Extra class 
Holiday 


HW3: Due Aug 20 
Aug 2024 
Extra class 
Holiday 


HW4: Due Aug 27 
Aug 2731 



QuizI, August \(31\) 
HW5: Due Sep 3 
Sep 37 


 
HW6: Due Sep 10 
Sep 1014 
Extra class 

Holiday 

HW7: Due Sep 17 
Sep 1721 
Extra class 


Holiday 
HW8: Due Sep 24 
Sep 2428 




HW9: Due Oct 1 
Oct 15 




HW10: Due Oct 8 
Oct 812 



QuizII, October \(12\) 
HW11: Due Oct 15 
Oct 1519 
Extra class 


Holiday 
HW12: Due Oct 22 
Oct 2226 




HW13: Due Oct 29 
Oct 29Nov 2 




HW14: Due Nov 5 
Nov 59 



Last day of class 
HW15: Due Nov 12 
Nov 2630 
EndSem, November \(27\) 



