Course 18.086: Mathematical Methods for Engineers II

Spring 2006: Room 3-370, MWF1

Department of Mathematics 
Massachusetts Institute of Technology 

o MESSAGE TO THE CLASS   I have read the projects and I am very satisfied -- I think you will be satisfied with course grades. If you don't need the copy I have, I will keep it. (Hongmei can pick hers up except pages 1-2.) I wrote small notes on the cover pages and Brett will have those any afternoon in 2-235. THANK YOU for taking the course.   Gilbert Strang

o Link to paper on "Approximate and Incomplete Factorizations"

o Is there a simple way to count the fill-in in elimination ?

Run chol (or lu) and use "nnz" (number of non-zeros).

 >> % Generate discrete Laplacian operator
 >> A=delsq(numgrid('S',100));
 >> % Choleskey factorize
 >> R=chol(A);
 >> nnz(R)
ans =

 >> % As above, but permute rows & columns by approximate minimum degree
 >> p=symamd(A);
 >> R=chol(A(p,p));
 >> nnz(R)
ans =

o Does min degree just take nodes a row at a time (if it breaks ties correctly)   If that is N^3 -- and would sparse backslash do it ?? --

Yes it does, it is a "greedy algorithm." The approximate one might be a little different, but in principle it does the same thing. Sparse backslash does this automatically. If symmetric, then it uses "symmmd" (symmetric minimum degree), then "chol." If non-symmetric, "colamd" (column approximate minimum degree), then umfpack.

o this is about as fast as possible except for Fast Poisson Solvers ?

Well, it is probably as fast as possible for Gaussian elimination. But iterative solvers do better, I think CG with Incomplete Choleskey should be N^(2.5). Then of course fast solvers, FFT-based and multigrid.

o Homework for Monday April 11 (start now please!!) from text pages 403-411 and also Section 3.6 of the "new book". Answer and turn in problems 1,2,3 in that Section 3.6

Develop a code for INCOMPLETE LU and try it on the 2D matrix for increasing N. You can make it a general code or specialize it to these particular matrices (and decide which entries to keep in the approximate factors L and U). Try on A2D u = random right side. You could use eig to find the spectral radius of the preconditioned matrix B. That matrix is I - inv(P)A2D where P ≈ LU. Of course if P = A2D then B = 0 and convergence in 1 step.

o Read sections 3.6 and 3.7 (later 7.2 and 7.4) from the new book   3.6   3.7   7.2   7.4

o Quiz on Friday March 11: Exact solutions and finite difference approximations to the equations discussed from Sections 6.4-6.6. Please bring printout of code and exact and approximate solutions at t=1 to the heat equation ut = uxx with u(x,0) = \delta(x). Choose any difference method and any stable \Delta t and \Delta x: grade does not depend on order of accuracy !

o M. Benzi, G. H. Golub and J. Liesen, "Numerical solution of saddle point problems", Acta Numerica, 14 (2005), pp 1-137 (to appear).
You can download the final version from

o Lecturer: Gilbert Strang, Office: 2-240. Office hours: Mon 3-4, Wed 2-3.

o Graders: Zhou Zhang ( and Fangyun Yang ( Office: 2-251. Office hour: Tues 11:30-12:30.

o Textbook: Introduction to Applied Mathematics by Gilbert Strang

o Course information:  (ps,pdf)

o Homework 1   Due IN CLASS WED 2/9 FRI 2/11 (stapled if possible)   PLEASE **PRINT YOUR NAME**   6.4: 1-5, 13-15, 22, 29;   6.5: 1-2, 17

o Homework 2   for FRIDAY FEB 25 MON FEB 28   6.5: 16 and 19 and (Find a stable difference method for ut = uxxx)   6.6: 1, 2, 5, 9   ALSO SOLVE ut + uux = 0 to t = 4 with u(x,0) = 1 and 0, also 0 and 1, as discussed in class (Lax-Friedrichs method).     Class MATLAB codes:   1   2   3   4   5

o No final.

o Exams: 2 or 3 mid-term exams. Open books and notes.

o Computational project.

o Homework: One problem set due in class each week, except exam weeks.

o Grading: Exams 50%, project 30%, homework 20%.

o Matlab: Documentation.

MIT Copyright © 2002 Massachusetts Institute of Technology