MIT 18.335: Introduction to Numerical Methods (Fall 2007)

Department of Mathematics
Massachusetts Institute of Technology
Evaluations: Current students: Please submit the online evaluations before Sunday, December 16.
Description: Advanced introduction to numerical linear algebra. Topics include direct and iterative methods for linear systems, eigenvalue decompositions and QR/SVD factorizations, stability and accuracy of numerical algorithms, the IEEE floating point standard, sparse and structured matrices, preconditioning, linear algebra software. Problem sets require some knowledge of Matlab.
Lecturer: Per-Olof Persson, Room 2-363A, Phone 617-253-4989, E-mail persson 'at' mit.edu, Office hours Tue 2-3pm in Room 2-363A.
Lectures: Room 1-390, MW 9:30-11
Teaching Assistant: Anshul Mohnot, E-mail anshulm 'at' mit.edu, Office hours Mon 4-5pm in Room 34-301.
Textbook: [NLA] Numerical Linear Algebra, Trefethen and Bau, SIAM 1997 (Books24x7 (MIT only), Lecture 1-5 Online, Quantum Books, Amazon, SIAM)
Other Readings: [Eig] Templates for the Solution of Algebraic Eigenvalue Problems: a Practical Guide, Bai et al, SIAM 2000 (HTML)
[It] Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods, Barrett et al, SIAM 1993 (PS, HTML)
[CG] An Introduction to the Conjugate Gradient Method Without the Agonizing Pain, Jonathan R. Shewchuk, August 1994 (PS, PDF)
[FP] What Every Computer Scientist Should Know About Floating Point Arithmetic, David Goldberg, ACM Computing Surveys, 1991 (CiteSeer)
Iterative Krylov-Subspace Solvers, Sivan Toledo (Lecture 21) (PDF)

Lecture slides will be provided on the course webpages
Grading: Homework assignments (60%), Midterm (40%)
Other webpages: Stellar (announcements, homework submissions, etc)

Fall 2006, Lecturer Per-Olof Persson (Math, Stellar, OCW)
Fall 2005, Lecturer Per-Olof Persson (Math, Stellar)
Fall 2004, Lecturer Plamen Koev (Math, OCW)
Fall 2001, Lecturer Dan Stefanica (Math)
Other links: MIT 18.06 Linear Algebra (for Linear Algebra review)
The MIT CDO Program (Computation for Design and Optimization, this class is one of the four core subjects)
The algorithm for MATLAB's backslash operator (from The Mathworks Online Documentation)
Policies, etc: Please start early with the homeworks, it might be hard to get help the last few days before they are due. Solutions will be given out soon after the due date; therefore there will be no extensions.

Collaboration on the homeworks is encouraged, but each student must write his/her own solutions, understand all the details of them, and be prepared to answer questions about them.

No books, notes, or calculators are allowed on the Midterm exam.
Exams: Midterm: Wednesday, Nov 7 (in-class: 9:30am-11:00am). Problems, Solutions
No books, notes, or calculators are allowed on the Midterm exam.
The midterm will cover:
  • Lectures 1-15
  • Textbook (Trefethen/Bau) lectures 1-17 and 20-28
  • Homeworks 1-4 and solutions
  • MATLAB codes on the webpage
Other preparation material (some more relevant than others):
Homework:
HW Due Date
1 Wed 09/19
2 Wed 10/03
3 Mon 10/22
4 Mon 11/05
5 Wed 11/28
6 Wed 12/12
Syllabus: NLA 38, Sh
Lec Date Topic Slides Readings Other
1 Wed 09/05 Introduction, Basic Linear Algebra Full, 2pp, 6pp NLA 1  
2 Mon 09/10 Orthogonal Vectors and Matrices, Norms Full, 2pp, 6pp NLA 2,3  
3 Wed 09/12 The Singular Value Decomposition Full, 2pp, 6pp NLA 4,5  
4 Mon 09/17 The QR Factorization Full, 2pp, 6pp NLA 6,7  
5 Wed 09/19 Gram-Schmidt Orthogonalization Full, 2pp, 6pp NLA 8 HW1 Due
  Mon 09/24 Student holiday - No lecture      
6 Wed 09/26 Householder Reflectors and Givens Rotations Full, 2pp, 6pp NLA 10  
7 Mon 10/01 Least Squares Problems Full, 2pp, 6pp NLA 11  
8 Wed 10/03 Floating Point Arithmetic, The IEEE Standard Full, 2pp, 6pp NLA 13, FP HW2 Due
  Mon 10/08 Columbus day - No lecture      
9 Wed 10/10 Conditioning and Stability I Full, 2pp, 6pp NLA 12,14,15  
10 Mon 10/15 Conditioning and Stability II Full, 2pp, 6pp NLA 16,17  
11 Wed 10/17 Gaussian Elimination, The LU Factorization Full, 2pp, 6pp NLA 20,21  
12 Mon 10/22 Stability of LU, Cholesky Factorization Full, 2pp, 6pp NLA 22,23 HW3 Due
13 Web 10/24 Eigenvalue Problems Full, 2pp, 6pp NLA 24,25  
14 Mon 10/29 Hessenberg/Tridiagonal Reduction Full, 2pp, 6pp NLA 26  
15 Wed 10/31 The QR Algorithm I Full, 2pp, 6pp NLA 27,28  
16 Mon 11/05 The QR Algorithm II Full, 2pp, 6pp NLA 29 HW4 Due
  Wed 11/07 Midterm     Midterm
  Mon 11/12 Veteran's day - No lecture      
17 Wed 11/14 Other Eigenvalue Algorithms Full, 2pp, 6pp NLA 30  
18 Mon 11/19 The Classical Iterative Methods Full, 2pp, 6pp It 2.2  
19 Wed 11/21 The Conjugate Gradients Algorithm I Full, 2pp, 6pp NLA 38, Sh  
20 Mon 11/26 Sparse Matrix Algorithms Full, 2pp, 6pp It 4.3, Eig  
21 Wed 11/28 Preconditioning, Incomplete Factorizations Full, 2pp, 6pp NLA 40, It 3 HW5 Due
22 Mon 12/03 The Conjugate Gradients Algorithm II Full, 2pp, 6pp  
23 Wed 12/05 Arnoldi/Lanczos Iterations Full, 2pp, 6pp NLA 33,36  
24 Mon 12/10 GMRES, Other Krylov Subspace Methods Full, 2pp, 6pp NLA 35,39, It 2.3  
25 Wed 12/12 Linear Algebra Software Full, 2pp, 6pp Eig HW6 Due
MATLAB Codes: Lecture 2, Vector Norms (lec2mldemo1.m), Induced Matrix Norms (lec2mldemo2.m)
Lecture 5, Classical and Modified Gram-Schmidt (lec5mldemo1.m, clgs.m, mgs.m)
Lecture 6, Householder QR Factorization (house.m, formQ.m)
Lecture 8, Floating Point Arithmetic (lec8mldemo1.m, num2bin.m)
Lecture 11, LU Factorization (lec11mldemo1.m, lec11mldemo2.m, mkL.m, mkP.m)
Homework 4, Banded Cholesky (bandtest.m)
Lecture 16, Jacobi Algorithm (lec16mldemo1.m, jacrot.m)
Lecture 17, Method of Bisection (lec17mldemo1.m, sturmcount.m), Divide-and-Conquer Algorithm (lec17mldemo2.m)
Homework 5, Linear Elasticity Utilities (assemble.m, elmatrix.m, mkmodel.m, qdplot.m, qdanim.m, allhw5.zip)
Lecture 19, Conjugate Gradients (cg.m, cg_stats.m)
Lecture 20, Elimination Movie (lec20mldemo1.m, realmmd.m)
Lecture 22, Conjugate Gradients (lec22mldemo1.m, steep.m, conjdir.m, conjgrad.m)
Lecture 23, Arnoldi Iteration (arnoldi.m)