Fast Multipole Methods: Fundamentals and Applications
Instructors: Ramani Duraiswami & Nail A. Gumerov
Course No. CMSC 878R/AMSC 698R
Note: non CS students must register for the course as AMSC 698R
http://www.umiacs.umd.edu/~ramani/cmsc878R/outline.html
Email: ramani@umiacs.umd.edu; gumerov@umiacs.umd.edu
class email: cmsc878r AT umiacs.umd.edu
Fall 2003, Tuesdays and Thursdays, 3:30 p.m. – 4:45 p.m.,
Homework is given on Thursdays at the end of the class
and due on the next
Tuesday at the beginning of class
Send class email
Lecture Notes
(Some of the material here is now also described in the book Fast Multipole Methods for the Helmholtz Equation in Three Dimensions (The Elsevier Electromagnetism Series))
DATE 
LECTURE 
CONTENTS 
09/02/2003 for viewing
for
printing

Lecture 1 
Introduction, Course rules, exams
Applications: Physics, Computer Vision, etc.
Simple example of factorization for degenerate kernel Asymptotic Complexity. Examples of complexity
Review of Publications.

09/04/2003 for viewing for printing

Lecture 2

Review of the factorization idea Structured Matrices Integral Equations
Fast Fourier Transform

Simple factorization example.
Intro to Matlab.


09/09/2003 for viewing for printing 
Lecture 3

Factorization Regular and Singular Expansions. Taylor Series, Error Analysis. 
09/11/2003 for viewing for printing 
Lecture 4

Series expansions for factorization Kronecker products Compression of series 
Homework 2  Solution  Fast Gauss transform based on Taylor Series 
09/16/2003 for viewing for printing 
Lecture 5

Near/Far Singular/Regular Expansions Example of S and R expansions of a singular function Error bounds 
09/18/2003 
Lecture 6

Class canceled due to Hurricane Isabel 
09/23/2003 for viewing for printing 
Lecture 6 
Splitting of the FMM sum Spatial ordering The PreFMM algortithm using R expansions and S expansions Optimization of the number of boxes in the PreFMM Complexity of the PreFMM 
09/25/2003 for viewing for printing 
Lecture 7  Introduction to translation operators 
Homework 3/4  Solution  Implementation of Data Structures for 1D PreFMM 
09/30/2003 for viewing for printing 
Lecture 8  (based on notes of previous lecture) 
10/02/2003 for viewing for printing 
Lecture 9  Single Level FMM (SLFMM) 
10/07/2003 for viewing for printing 
Lecture 10  Review 
10/09/2003 for viewing for printing 
Lecture 11  Multilevel FMM 
Homework 5  Solution  S, R and SR translation in one dimension. Error bounds 
10/14/2003 for viewing for printing 
Lecture 12  Hierarchical Data Structures for space subdivision 
10/16/2003 for viewing for printing 
Lecture 13  Hierarchical Data Structures for space subdivision 
Homework 6  Solution  
10/21/2003 for viewing for printing 
Lecture 14  Bit interleaving and deinterleaving 
10/23/2003  Mid Term Exam  Solution 
Homework 7  Solution  Data Structures 
10/28/03 for viewing for printing 
Lecture 15  Introduction to iterative methods for use with the FMM 
10/30/03 for viewing for printing 
Lecture 16 
Review of Exam and previous class Complexity of MLFMM 
Homework 8  1D MLFMM  
11/02/03 for viewing for printing 
Lecture 17 
Review of MLFMM Error analysis of the MLFMMI Project Info. 
11/04/03 for viewing for printing 
Lecture 18 
Error analysis of the MLFMMII 
Homework 9  Project Preliminary report (See Lecture 17)  
11/11/03 for viewing 
Lecture 19  FMM for the Gravitational/Coulombic potential. Introduction to Spherical Harmonics. 
11/13/03  Lecture 20*  Guest Lecture by Zhihui Tang: Fast translation operators for the Laplace equation in 2D and 3D based on structured matrix decompositions 
Homework 10  Project Report: S, R, SS, SR , RR operator evaluation  
11/18/03  Lecture 21*  General theory of diagonal forms for the FMM 
11/20/03 for viewing 
Lecture 22  Theory of the adaptive FMM 
11/25/03 for viewing 
Lecture 23 
Adaptive FMM from Cheng et al (1999) Connection between the FMM and Boundary Element Methods 
12/02/03  Lecture 24  Some research ideas/directions. Review 
12/04/03  Project Reports 1 
1. Yang Wang: A Javabased animated implementation of
the FMM in 2D 2. Zhenyu Zhang: FMM for the solution of an eigenvalue problem for a surface integral operator in 3D 3. Karthikeyan Duraisamy: Fast particle methods for the simulation and control of 3D Vortex Wakes from Lifting Wakes 4. Zhiyun Li: Nonuniform Fast Fourier Transforms 
12/09/03  Project Reports 2 
5. Weigong Zhang: Fast summation of Helmholtz monopoles
in 2D. 6. Alap Karapurkar: The Fast Multipole Method for Diffuse Light Scattering 7. Shaju John and S. Koushik: Simulation of ferromagnetic particle chain formation in a fluid medium under the action of a magnetic field 8: Shreyas Ananthan and Sandeep Gupta: Fast Multipole Methods for Particle Simulations in Vortex Dominated Flows All project final reports are due on this day. 
12/11/03  Final  Solution 
* These lectures have been distributed as hardcopy, since they are based on as yet unpublished research.