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
E-mail: 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
d-dimensions.
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.
S|S,
R|R, S|R
operators
|
|
Lecture 8 |
Single level FMM
Requirements for functions in FMM. SLFMM.
Formalization of FMM. SLFMM and optimization.
|
|
S|R
translation operator for (x-y)-1.
Error bounds.
|
||
Lecture 9 |
Data Structures. 2d-trees.
Need for data structures.
2d
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 (x-y)-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 bit-interleaving |
||
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.
D-trees
and C-forests.
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 (x-y)-1 in
1-D |
|
Lecture 18 |
Error bounds for the MLFMM
Example problems (1 and 2 D).
Error bounds and optimization.
S|S,R|R,
and S|R-translation 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.
Rotation-coaxial 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 |
Guest-Lecture 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 S-C transform (
·
kernel
methods in statistical learning (
·
Inverse electromagnetics in 2D ( |
|