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.,
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, "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
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
k-nearest-neighbors and n-body 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: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 | 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