Syllabus

A unified introduction to the theory and practice of modern, near linear-time, numerical methods for large-scale partial-differential and integral equations. Topics include: preconditioned iterative methods; generalized Fast Fourier Transform and other butterfly-based methods; multiresolution approaches including multigrid algorithms, hierarchical low-rank matrix decompositions, and low and high frequency Fast Multipole Methods. Example applications include: aircraft design, cardiovascular system modeling, electronic structure computation, and tomographic imaging.

Grad H subject. Units: 3-0-9. The class is suitable for graduate students from all departments who have affinities with mathematics.

Topics:

Introduction: PDE vs. integral equations, Fourier-based numerical methods.

Exterior problems:

• Surface integral equations, layer potentials
• The Fast Multipole Method (FMM)
• Partitioned low-rank methods, cross-approximation
• Applications to electrostatics, biomolecules, potential flows

Interior problems and variable media:
• Multigrid and relaxation
• Volume integral equations
• Applications to fluid and heat flows, dieletrics, electronic density

High-frequency problems:
• High-frequency FMM
• Butterfly algorithms
• Applications to acoustic and electromagnetic scattering, radar imaging

Prerequisites: Familiarity with ordinary differential equations, partial differential equations, Fourier transforms, linear algebra, and basic numerical methods for PDE, at the level of 18.085. The assignments will involve computer programming in the language of your choice (Matlab recommended).

Figures: top-right, the hierarchical tree structure of the butterfly algorithm. Bottom-left, low-rank interactions in the electromagnetic far-field

Reference material

Here is the current version of the class notes by Laurent Demanet: 04/23/2014

Three references covering background material on numerical methods for PDE.

Four references covering material on boundary integral equations.

• 09/07/17 Lecture 1: Slides
• 09/12/17 Lecture 2: Lecture notes
• 09/14/17 Lecture 3: Lecture notes
• 09/19/17 Lecture 4: Lecture notes
• 09/21/17 Lecture 5: Slides
• 09/26/17 Lecture 6: Lecture notes
• 09/28/17 Lecture 7: Slides
• 10/05/17 Lecture 9: Slides
• 10/12/17 Lecture 10: Slides
• 10/17/17 Lecture 11: Slides
• 10/19/17 Lecture 12: Slides
• 10/24/17 Lecture 13: Slides
• 10/26/17 Lecture 14: Lecture notes
• 10/31/17 Lecture 15: Lecture notes
• 11/02/17 Lecture 16: Guest lecture by Steven Johnson
• 11/07/17 Lecture 17: Lecture notes
• 11/09/17 Lecture 18: Slides
• 11/14/17 Lecture 19: Lecture notes
• 11/16/17 Lecture 20: Slides
• 11/21/17 Lecture 21: Lecture notes

Who, when, and where

Date and Time: TR, 1:00-2:30, room 2-143.
Instructor: Carlos Perez-Arancibia.
Office hours: Email instructor.

Evaluation

50% homework, 50% course project.

The homework problem sets will consist of both theoretical problems and numerical experiments. No late copy will be allowed. The lowest score will be dropped. Collaboration is allowed, but the codes and copies you turn in must be original and written by you.

Problem set 1: Due date October 11th, hand in at the end of the class. Here are the notes on the low-order collocation method discussed in class. Here is a simple implementaiton of the collocation method for the numerical solution of the Helmholtz equation using the indirect single-layer formulation.

Problem set 2: Due date November 2nd, hand in at the end of the class.

Problem set 3: Due date November 21st, hand in at the end of the class. MRI permittivity model: 257x257 data set and 1025x1025 data set.

The course project will be of a computational or mathematical nature. Each student will have a different project (hopefully tailored to their taste). The project report should be written like a publication: clear and concise. It is a good idea to use LaTeX for the typesetting.

Here is a list of possible project topics.

Important dates:

• Choose a project by the beginning of November. Requires consent of the instructor.
• Progress checkup: mid-November (schedule a meeting with the instructor).
• Project presentations: 12/07 and 12/12.
• Project report due: 12/12.