Course 18.086: Mathematical Methods for Engineers II
(Spring 2006)

Department of Mathematics 
Massachusetts Institute of Technology 

o Please email your project reports to: !!!

o MINIMUM DEGREE MOVIE: nodes_movie_edges.m (also need realmmd.m)
o ANOTHER GREAT CODE (actually 2!) WAS JUST RECEIVED (FRIDAY 5PM) FROM ADITYA UNDURTI: lax_wendroff.m, lax_friedrichs.m
o MORE GREAT CODE (wave propagation), FROM FRED PEARCE: fdwe_1D.m, get_ricker.m

o Lecturer: Gilbert Strang, Office: 2-240. Office hours: MW 3

o Lecture: MWF 1 in room 3-370

o Grader: Yeunwoo Cho, Office: 2-130. Office hour: F 3 (starting 2/17)

o Textbook: Introduction to Applied Mathematics by Gilbert Strang

o Course information:  (ps,pdf)

o Good information about the course is available on OpenCourseWare !!!   18.086 on OCW

o No final.

o Selected Project from 2006

o Computational projects:

o Homework #1 (for Monday 2/13 if possible):   (ps,pdf)       Solutions:  pdf    HW1-codes

axis equal,grid on

o MATLAB codes:   AB_2.m     f_is.m     HW1_1.m     HW1_2.m     RK_2.m

o Homework #2 (for Friday March 3rd):   (ps,pdf)       Solutions:  pdf    HW2-codes

o Level Set Material:   lecture notes (pdf)     presentation (pdf)     lsdemo (m-files)

o Project #1 (for Wednesday April 5th):   (pdf)      

o Sections from the new book Applied Mathematics and Scientific Computing (2007):

o Matlab Documentation:

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));
 >> % Cholesky 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 Cholesky should be N^(2.5). Then of course fast solvers, FFT-based and multigrid.

o 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 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

MIT Copyright © 2002 Massachusetts Institute of Technology