Fast Multipole Methods: Fundamentals and Applications
Instructors: Ramani Duraiswami & Nail A. Gumerov
Course No. CMSC 878R/AMSC 698R/MAIT 627
Email:
ramani AT umiacs.umd.edu;
gumerov AT
umiacs.umd.edu
Fall 2006, Mondays and Thursdays, 5:00 p.m. – 7:45 p.m.,
Homework is given on Wednesdays at the end of the class and due on the next Wednesday at the beginning of class
Lecture Notes from previous years 2004 2003 2002
(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))
The course outline below is a tentative organization of the material. It is subject to change!
DATE 
LECTURE 
CONTENTS 

09/05/2006 
Introduction, Course rules, exams
Applications: Physics, Computer Vision, etc.
Simple example of factorization for degenerate kernel
Asymptotic Complexity. Examples of complexity
Structured Matrices Fast Fourier Transform The factorization idea Applications of the FMM 
D. Donoho, "HighDimensional Data Analysis: The Curses and Blessings of Dimensionality," AMS Lecture at a Conference on "Math Challenges of the 21st Century"
Steele Prize Announcements, 2001
C. Moler, Numerical Computing with Matlab, 2004, (available online) 

(due 09/12/2006) 

Simple factorization example.
Remember to label axes in all plots. 

09/12/2006 
Function representation; Local expansions and Far Field Expansions Taylor Series and error bounds 1D Fast Gauss Transform
Multidimensional series; 
V. Raykar et al. "Fast computation of sums of Gaussians in high dimensions, " UMD CS TR 4767 

Homework 2 (due 09/19/2006) 
Expansions for Fast Gauss Transform; 1D IFGT  
09/19/2006  Lecture 3 
Singular kernels; well separated clusters; 
P.B.
Callahan and S. R. Kosaraju "A
decomposition of multidimensional point sets with applications to
knearestneighbors and nbody potential fields"

Homework 3  Expansions/ Pre for the Cauchy Kernel in 1D  
09/26/2006  Lecture 4  Translation operators; single level fast multipole method; Error and Complexity Analysis  A. Dutt, M. Gu, V. Rokhlin "Fast Algorithms for Polynomial Interpolation, Integration, and Differentiation," SIAM J. Num. Anal., 33:16891711, 1996 
Homework 4  Single level FMM for Cauchy Kernel  
10/03/2006  Lecture 5  Multi Level Fast Multipole Method Error and Complexity Analysis  Java
Applet Yang Wang's thesis 
Homework 5  Implement the multilevel fast multipole method in 1D  
10/10/2006  Lecture 6  Data Structures; Neighbor finding; Computational Geometry  H. Samet, Computing Surveys, (1984) 
Data structures in multiple dimensions  
10/17/2006  Lecture 7  Data Structures for IFGT in high dimensions;
Complexity of the MLFMM

Matlab implementation 
Homework 7 (due 10/31) 
Project selections due Project Suggestions 

10/24/2006  Exam 1  (Half the lecture)  
10/24/2006  Lecture 8  (Second half of the lecture) 
Nishimura paper Beatson and Greengard 
10/31/2006  Lecture 9  Continuation of error bounds Iterative Methods and the FMM 

11/07/2006  Lecture 10  2D Laplace; Spherical Harmonics; Multipoles; Laplace Equation in 3D; 
Greengard and Rokhlin, 1987 
Homework 8  
11/14/2006  Lecture 11  Diagonal Forms; Matrix decompositions of Translation Operators  
Homework 9  
11/21/2006 
Lecture 12
Adaptive 
Helmholtz Equation; Wavelength dependence Fast translational methods; Elements of Group Theory; Adaptive FMM 
Coiffman et al., 1997;
Gumerov & Duraiswami, 2004 (Chapter 1 available free online)
Rokhlin, 1993

Interim Project Report Due  
11/28/2006  Lecture 13  NUFFT FFTM 
Cheng et al, 1997; Gumerov & Duraiswami 2004 
12/05/2006  Lecture 14  Review Project Reports  1 

12/12/2006  Lecture 15  Project Reports  2 Project Reports  3 
Other References