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 AT umiacs.umd.edu; gumerov AT umiacs.umd.edu
class email: cmsc878r AT umiacs.umd.edu
Fall 2002, Tuesdays and Thursdays, 12:30 p.m. – 1:45 p.m.,
Send class email
Lecture Notes
(Note: 03/10/2005 : 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 
Lecture 1 
Introduction
Applications: Physics, Computer Vision, etc.
Simple example of factorization for degenerate kernel


Lecture 2

FMM
in General Terms.
Review of Publications.
Asymptotic Complexity. Examples of complexity


Simple factorization example.
Intro to Matlab.


Lecture 3

Factorization.
Local expansions. Far and local expansions.


Lecture 4 
Multidimensional
Kronecker product. Dot product.
General form of factorization.
Properties of Kronecker and dot product.


Middleman factorization for sums of Gaussians using


Lecture 5 
Compression of multidimensional series.
Compression operator. Complexity in
ddimensions.
Use
of compression in multidimensional FMM.


Lecture 6 
Far
field expansions.
Functional analysis review.
Basis functions. Far field expansions.
Examples of far field expansions (power, asymptotic)


Multidimensional middleman for FGT and use of the “Compression” operator.


Lecture 7 
Operators in space of coefficients.
Truncation operators.
Translation operators.
Operator norms. Errors.
SS,
RR, SR
operators


Lecture 8 
Single level FMM
Requirements for functions in FMM. SLFMM.
Formalization of FMM. SLFMM and optimization.


SR
translation operator for (xy)^{1}.
Error bounds.


Lecture 9 
Data Structures. 2^{d}trees.
Need for data structures.
2^{d}
trees. Parents, children, etc.
Hierarchical space subdivision.


Lecture 10 
Data Structures. Bit interleaving and spatial ordering.
Neighbor search.
Threshold level of space subdivision.


Single Level FMM for (xy)^{1}.
Error bounds 

Lecture 11 
Multilevel FMM.
Structure of the algorithm.
Setting data structure.
Upward Pass.
Hierarchical domains and potentials.
Upward Pass. 

Lecture 12 
Multilevel FMM.
Downward Pass.
Asymptotic Complexity of the MLFMM.
Downward Pass. Complexity of each step.


Bookkeeping routines necessary for MLFMM based on bitinterleaving 

Lecture 13 
Multilevel FMM.
Optimization.
Results of MLFMM tests.
Dependence of FMM performance on parameters.


Review of concepts. 

Lecture 14 
Adaptive multilevel FMM.
Data structures.
Dtrees
and Cforests.
Adaptive MLFMM algorithm.


Lecture 15 
Discussion of multilevel FMMs
Data structures and elements of the algorithms.
More insight into the MLFMM.
Neighborhoods and dimensionality. 

Lecture 16 
Methods for solution of linear systems
Iterative methods (Conjugate gradient, Krylov,
etc.)
Use
of the FMM in iterative solvers.


Lecture 17 
Error bounds for the MLFMM.
A
scheme to obtain the error bounds.
Error for sequences of translations.


Solution

MLFMM for (xy)^{1} in
1D 

Lecture 18 
Error bounds for the MLFMM
Example problems (1 and 2 D).
Error bounds and optimization.
SS,RR,
and SRtranslation errors.
Examples.


Lecture 19 
Some application of the MLFMM.
2D,
3D potential fields, particle simulations, RBF.
Complex potentials. Example problems.


Lecture 20 
3D
problems and vector analysis.
Boundary element method.
Reduction of 3D problems to forms for FMM use.
Spherical Harmonics.


Lecture 21 
(Guest Lecturer:
Fast spherical transform and applications.
Spherical harmonics. Properties.
Algorithm. Introduction, examples, and computational
results .


Lecture 22 
3D
Multipoles.
Translation theory.
Recursive computations.
Rotationcoaxial translation decomposition.
Multipoles.
Differentiation/recursion.


Lecture 23 
Research directions in the FMM.
Identification of problems and possible ways of their solution.
Scaling, adaptivity, etc.


Lecture 24 
Integral transforms and fast translations.
Integral transforms. Signature function.
Sparse matrix decomposition.
Examples for the 3D Helmholtz equation. 

Lecture 25 
This review of the course 


Lecture 26 
GuestLecture by
*CANCELLED DUE TO THE WEATHER* 

Lecture 27 
Project reports :
FMM
for
·
Fast Gauss Transform in multiple dimensions (
· Fast
vortex methods in 2D (
· Thin
plate splines in 2D (
·
Vortex
methods in 3D (
·
Multiquadrics in 3D (
·
Conformal
mapping using the SC transform (
·
kernel
methods in statistical learning (
·
Inverse electromagnetics in 2D ( 
