Fast Multipole Methods: Fundamentals and Applications

 

Instructors: Ramani Duraiswami  & Nail A. Gumerov

Course No. CMSC 878R/AMSC 698R/MAIT  627

E-mail: ramani AT umiacs.umd.edu;

gumerov AT umiacs.umd.edu

 

Fall 2006, Mondays and Thursdays, 5:00 p.m. 7:45 p.m.,

Location: CSI 3120

 

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

READING

09/05/2006

 

Lecture 1

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

 G. Moore, "Cramming More Components onto integrated circuits," Electronics, 38, 1965

 

D. Donoho, "High-Dimensional Data Analysis: The Curses and Blessings of Dimensionality," AMS Lecture at a Conference on "Math Challenges of the 21st Century"

 

Steele Prize Announcements, 2001

 

Top Ten Algorithms.

 

C. Moler, Numerical Computing with Matlab, 2004, (available online)

 Homework 1

(due 09/12/2006)

 

Simple factorization example.

Remember to label axes in all plots.

 

09/12/2006

 Lecture 2

Function representation;

 Local expansions and Far Field Expansions

Taylor Series and error bounds

1D Fast Gauss Transform

Multidimensional series;
series compression;

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 Using the example of the Cauchy kernel in 1-D the following concepts are introduced:

Singular kernels;  well separated clusters;
Space partitioning;  pre-FMM;  Deriving  Error Bounds; Deriving complexity estimates; Complexity at a given error bound; Optimization of  problem parameters

P.B. Callahan and S. R. Kosaraju "A decomposition of multidimensional point sets with applications to k-nearest-neighbors and n-body potential fields"
Journal of the ACM, 42:67-90, 1995.

 

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:1689-1711, 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 multi-level 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

Part 2

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

 demo1

demo2

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

 

L. Greengard and J. Strain, "The Fast Gauss Transform,"  SIAM J. Sci. and Stat. Comput. 12, 79 (1991)