18.335 Numerical Methods of Applied Mathematics I

Fall 1997 Class

Fall, 1996
Monday/Wednesday 11:00--12:30
1-390
Prof. Alan Edelman

We recognize that every engineering and science department at MIT has significant numbers of graduate students using and developing sophisticated computer simulations. These students often develop software by learning numerical analysis from either a basic textbook or from an applications specific class. While these approaches may well serve the immediate needs of an application, many students wish a deeper understanding of new more efficient and sophisticated techniques. For this reason, Professors Jacob White and Alan Edelman have joined forces towards the creation of a curriculum at MIT geared towards the study of numerical algorithms. In the future, we hope faculty from other departments may well join us. (There are over fifty classes at MIT with the word numerical in the description.) Our particular focus are areas where there has been much active research in algorithms themselves.

Students interested in a solid background in modern numerical methods are encouraged to take this course and 6.336 this fall. In addition, students are well advised to learn about the differential equation approaches taught this spring in 18.336 taught by Professor Brenner focusing on finite difference methods, spectral methods, etc., and 18.337 , the latter will probably emphasize the domain decomposition method of differential equations, the multipole algorithm for N-body problems, some sparse matrix techniques, and programming of symmetric multiprocessors (the latest nodes for parallel computers!). Of course students should learn as much as possible about applications, computing, and/or mathematics, depending on interest and department. Professor Edelman, of the mathematics department, believes that mathematical principles are crucial for understanding algorithms intellectually (the science of numerical analysis), but coding is important to really get to know an algorithm (the engineering of numerical analysis).

Topics for 1996: IEEE arithmetic, heavy concentration on modern iterative methods and the multigrid method, will also cover eigenvalue and dense methods. Many students really learn their linear algebra in this course. Students who feel on shaky ground with linear algebra have survived quite well in this class, but often with the "security blanket" of a text such as Strang's Linear Algebra and its applications (18.06). We will have two in class exams, and no final. Course texts are Saad, Briggs, and Golub and van Loan 3rd edition (not available yet).

Problem Sets

Homework #1: Due Monday Sep 16, 2.1 through 2.9, 2.12, 2.17, 2.25 (Count zero as a normal if you like.)

Homework #2: Due Wednesday Sep 25, Saad page 119: 1ab(do not relate to chapter 2), 2, 3, 4, 5, 8. If A is SPD and A-H'AH is pos def, show that the spectral radius of H is less than one. Use this to prove Theorem 4.6.

Homework #3: Due Monday Due Monday October 7. This is a test of resourcefulness more than mathematics. The idea is to try out using a package with all of the difficulties and benefits of such an approach. Recognizing the importance of software tools rather than writing one's own code, I would like you to look at two sources of iterative solver codes and report on them. Feel free to work in teams and submit a joint report if you choose. One iterative solver BPKIT was recently announced. Try doing the BPKit assignment . You may prefer instead to try the C++ suite IML++ on the same problems. Perhaps the matlab templates in mltemplates.shar off the templates page is the easiest yet. You should give a few comments as to whether you recommend this software to others, and which methods worked best, and what problems arose. Feel free to look for other sources on the web. Have fun with this assignment, and do not worry too much about what to hand in other than showing me that you learned something. Rather be concerned as to whether you feel you can use this software. (I will update this assignment as I get feedback.) In any event, do run the algorithms on the matrices.

Homework #4: Due Wednesday October 16. Do the handout problems on page 302 and 306.

Homework #5: Due Wednesday, November 13. 7.1 (page 318):1,3,8,10; 7.2 (page 327):2,10; 7.3 (page 339): 3,4; 7.4 (page 350): 3,6,10; 7.5 (page 361): 1,2; 7.6 (page 372): 6.

Homework #6: Due Wednesday, November 27. We are lucky to get a sneak preview of Jim's Demmel's new book on numerical linear algebra. Looks like the killer programming assignment is Question 4.16 on page 211. So let's give that one a try. Here are pages 201--216 in postscript form. You may need Theorems 4.4 and 4.5 .

Current Lecture Plan

Lecture 1: (9/4) Introduction to Numerical Methods, conditioning, stability
- Why IEEE exception handling matters
Lecture 2: (9/9) The IEEE Floating Point Standard and The Mathematics of the Intel Pentium Flaw
Lecture 3: (9/11) The classical Iterative Methods
Lecture 4: (9/16) Convergence Analysis of Classical Iterative Methods
Lecture 5: (9/18) The Conjugate Gradient Algorithm
- Also see Conjugate Gradient Method Without Agonizing Pain, by Jonathan R. Shewchuk (postscript)
(9/23) Student Holiday
Lecture 6: (9/25) Convergence Analysis of Conjugate Gradient
Lecture 7: (9/30) Preconditioned Conjugate Gradient
Lecture 8: (10/2) Common Matrix Factorizations,
Lecture 9: (10/7) CGNR, CGNE,The Arnoldi Method and GMRES
Lecture 10: (10/9) Unsymmetric Methods, GMRES
(10/14) Columbus Day
Lecture 11: (10/16) BCG, QMR, Review
Lecture 12: (10/21) First Exam
Lecture 13: (10/23) Optimization: Sequential Quadratic Programming
Lecture 14: (10/28) The symmetric eigenvalue problem
Lecture 15: (10/30) Unsymmetric eigenvalue methods
Lecture 16: (11/4) Model-order reduction?
Lecture 17: (11/6) Wavelets and matrix sparsification?
- Wavelet Compression Applet
- Use WAVEMENU in matlab
- Wavelet Papers
- Introductory Material
- Gil Strang's Intro press on Brief Intro
(11/11) Veterans Day
Lecture 18: (11/13) Dense Linear Systems, Gaussian Elimination
Lecture 19: (11/18) Linear Systems, Perturbation Theory
Lecture 20: (11/20) FFT
Lecture 21: (11/25) Extrapolation Theory
Lecture 22: (11/27) Introduction to Multigrid
Lecture 23: (12/2) The Multigrid Algorithm
Lecture 24: (12/4) Analysis of Multigrid
Lecture 25: (12/9) Completion of Multigrid and review
Lecture 26: (12/11) Second Exam

Documentation

Matlab Primer (postscript)
Matlab On-line Reference
GAMS - Guide to Available Math Software
A search facility to find numerical software

Maintained by Alan Edelman Last modified: August 16, 1996
This document may be reached with the shortened address http://web.mit.edu/course/18/18.335/WWW/home