Numerical Linear Algebra
August - November 2013

Lectures:	Monday and Wednesday from 10:30 to 11:45
Classroom:	Lecture Hall 3
Instructor:	Kavita Sutar-Deshpande
Contact:	Office: 403
	phone: 962
	email: ksutar AT cmi DOT ac DOT in
Office Hours:	Thursdays from 2:00 to 3:00 p.m. (If you cannot make it to my office hours but wish to meet me, please send me an email to set up an appointment at a mutually convenient time)
Texts:	Numerical Linear Algebra by Lloyd N. Trefethen and David Bau III, SIAM. Reference books: Introduction To Numerical Linear Algebra And Optimisation by P.G. Ciarlet. Applied numerical linear algebra by James Demmel. Introduction to Linear Algebra by Gilbert Strang.
Teaching Assistant:	Md Shariq; email: shariq AT cmi DOT ac DOT in
Recitations:	Lecture hall 1 on Tuesday 2:00 to 3:30 p.m. (every two weeks; please see schedule for details)
Grading:	25 % - Mid-semester exam 30 % - Final exam 10 % - Recitation 15 % - Homework 15 % - Project and presentation 5 % - Instructor's discretion (based on participation in the course) All grades will be uploaded on Moodle.

Course syllabus

Review of linear algebra (vector spaces, linear maps, matrix of a linear transformation, effect of change of basis, Hermitian, normal and unitary matrices, inner product and norms, eigenvalues and eigenvectors, diagonalisable matrices, Jordan normal form, other reductions of matrices, singular values).
Matrix norms, Rayleigh quotient.
Introduction to conditioning and stability.
Gaussian elimination, LU decomposition, Cholesky factorisation (algorithms, operation counts, conditioning and stability issues for these methods).
Least squares problems.
QR factorization, Gram-Schmidt orthogonalisation, Householder's method.
The singular value decomposition and its applications
Iterative methods for solving linear systems: the method of conjugate gradients, Gauss-Seidel, successive over-relaxation.
Eigenvalue problems.
Using scilab.

Course components

The course will consist of in-class lectures during all weeks of the semester. Homework will be assigned every week (barring only exam weeks). Recitations will be held twice a month. Students will work in groups on a project during the semester and presentations will be in November. There will be a midterm exam in September and a final exam at the end of the semester.

Homework

Homework will be posted on this website every Sunday night and will be due in one week (on the following Monday).
You may pick up the graded homework on Tuesdays (during recitation or in my office).

Late submissions will carry penalties.
You may work alone or in groups to do your homework. In any case, you must write your own solutions.

Attendance

Attendance to classes is not required but absences will be noted. Explanation for longer absences (more than one class) is required.
Attendance in recitations is required.

Project

Your project should be connected to numerical linear algebra. It can be either Scilab or Python based. In your proposal, you should outline the importance of your project and its feasibility.
There should also be a survey of the literature related to your project. The project and presentation schedule will be as follows:

Monday, August 26: submit project proposal.
Monday, September 16: progress report 1.
Monday, October 7: progress report 2.
November 5, 12: project presentations.
Friday, November 15: project submission.

All submissions must be typeset in LaTeX. Each group will get 30 minutes for the presentation. Ideally, a presentation should include a description of your problem, your study, the present state of the problem, an example and a conclusion. Each member of the group should be actively involved in the presentation. Please allow 5 minutes of your time for possible questions from the audience.

Warning against copying/plagiarism

Please be warned that I will not tolerate any kind of plagiarism in your work. You are free to search for ideas on the internet and in books but the details and work have to be your own.

According to the Merriam-Webster OnLine Dictionary, to plagiarize means:

to steal and pass off (the ideas or words of another) as one's own
to use (another's production) without crediting the source;
to commit literary theft;
to present as new and original an idea or product derived from an existing source.

Synonyms: copying, appropriation, infringement, piracy, counterfeiting, theft, borrowing.

Please visit www.plagiarism.org for more details.

Schedule

Week	Topic
1 (05/08 - 09/08)	Review of linear algebra; orthogonal vectors and matrices (TB: Chap. 1, Lecture 2). Homework 1 (due on 12/08)
2 (12/08 - 16/08) Recitation on 13/08	Matrix norms; Rayleigh quotient. Homework 2 (due on 19/08)
3 (19/08 - 23/08) Recitation on 20/08	Problems in numerical linear algebra; conditioning and stability issues; Singular value decomposition. Introduction to Scilab and LaTeX. Homework 3 (due on 26/08) Project proposal (due on 26/08)
4 (26/08 - 30/08) Recitation on 27/08	Gaussian elimination, LU factorization; partial and complete pivoting; algorithms for GE; operation count and stability of GE; Homework 4 (due on 02/09)
5 (02/09 - 06/08 ) (EXTRA CLASS on 03/09)	Cholesky factorization; projection matrices; Gram-Schmidt orthogonalization; intro to QR factorization. Homework 5 (due on 10/09)
6 (09/09 - 13/09) Recitation on 10/09	Holiday on 09/09 (Vinayaka Chaturthi); no class on 11/09; both classes to be covered on other days. Homework 6 (due on 16/09).
7 (16/09 - 20/09)	QR factorization using Householder's method; Iterative methods: Jacobi, Gauss-Seidel, SOR. Homework 7 (due on 23/09) Project report I (due on 16/09)
8 (23/09 - 27/09)	Mid-semester exams week.
9 (30/09 - 04/10) Recitation on 01/10	Iterative methods (continued). Holiday on 02/10 (Gandhi Jayanthi). Homework 8 (due on 07/10) Project report II (due on 07/10)
10 (07/10 - 11/10)	Least squares problems; intro to eigenvalue problems; power method, inverse iteration. Homework 9 (due on 14/10)
11 (14/10 - 18/10) Recitation on 15/10	Power method, inverse power method, Rayleigh quotient iteration; reduction to Hessenberg or tridiagonal form. Holiday on 14/10 (Vijaya Dasami)
12 (21/10 - 25/10)	QR algorithm.
13 (28/10 - 01/11) Recitation on 29/10	Jacobi method, bisection method, divide-and-conquer. Homework 10 (due on 15/11)
14 (04/11 - 08/11)	Computing SVD, Golub-Kahan bidiagonalization. Project presentations on 05/11
15 (11/11 - 15/11) Recitation on 12/11	Project presentations on 12/11 Project submission (due on 15/11)
16 (18/11 - 22/11)
17 (25/11 - 29/11)	Final exams

PROJECT REPORTS:

1) Analysis of price fluctuations of financial stocks and construction of stock portfolios - Tvisha Gupta, Abhishek Behera.
2) Image compression - Sunny Verma, Jakkam Phanindra Krishna.
3) Study of population growth and intrinsic growth rate - Biswajit Mahato, Srijan Datta.
4) Iterative methods for the eigenvalue problem - Radharaman Roy, Mouktik Chattopadhyay.

Back to my teaching page

Numerical Linear Algebra August - November 2013

Homework

Numerical Linear Algebra
August - November 2013