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


class email: cmsc878r AT


Fall 2003, Tuesdays and Thursdays, 3:30 p.m. 4:45 p.m.,

Location: CSI 2118


Homework is given on Thursdays at the end of the class and due on the next
Tuesday at the beginning of class


Course Outline

Send class email

Lecture Notes

(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))





for viewing

for printing  

Lecture 1

Introduction, Course rules, exams

Applications: Physics, Computer Vision, etc.

Simple example of factorization for degenerate kernel

Asymptotic Complexity. Examples of complexity

Review of Publications.


for viewing

for printing


Lecture 2

Review of the factorization idea

Structured Matrices

Integral Equations

Fast Fourier Transform

Homework 1

Scribe Notes

Simple factorization example.

Intro to Matlab.


for viewing

for printing

Lecture 3


Regular and Singular Expansions. Taylor Series,

Error Analysis.


for viewing

for printing

Lecture 4 Series expansions for factorization
Kronecker products
Compression of series
Homework 2 Solution Fast Gauss transform based on Taylor Series
for viewing
for printing
Lecture 5 Near/Far Singular/Regular Expansions
Example of S and R expansions of a singular function
Error bounds
09/18/2003 Lecture 6 Class canceled due to Hurricane Isabel
for viewing
for printing
Lecture 6 Splitting of the FMM sum
Spatial ordering
The Pre-FMM algortithm using R expansions and S expansions
Optimization of the number of boxes in the Pre-FMM
Complexity of the Pre-FMM
for viewing
for printing
Lecture 7 Introduction to translation operators
Homework 3/4 Solution Implementation of Data Structures for 1-D Pre-FMM
for viewing
for printing
Lecture 8 (based on notes of previous lecture)
for viewing
for printing
Lecture 9 Single Level FMM (SLFMM)
for viewing
for printing
Lecture 10 Review
for viewing
for printing
Lecture 11 Multilevel FMM
Homework 5 Solution S, R and S|R translation in one dimension. Error bounds
for viewing
for printing
Lecture 12 Hierarchical Data Structures for space sub-division
for viewing
for printing
Lecture 13 Hierarchical Data Structures for space sub-division
Homework 6 Solution
for viewing
for printing
Lecture 14 Bit interleaving and deinterleaving
10/23/2003 Mid Term Exam Solution
Homework 7 Solution Data Structures
for viewing
for printing
Lecture 15 Introduction to iterative methods for use with the FMM
for viewing
for printing
Lecture 16 Review of Exam and previous class
Complexity of MLFMM
Homework 8 1-D MLFMM
for viewing
for printing
Lecture 17 Review of MLFMM
Error analysis of the MLFMM-I
Project Info.
for viewing
for printing
Lecture 18 Error analysis of the MLFMM-II
Homework 9 Project Preliminary report (See Lecture 17)
for viewing
Lecture 19 FMM for the Gravitational/Coulombic potential. Introduction to Spherical Harmonics.
11/13/03 Lecture 20* Guest Lecture by Zhihui Tang: Fast translation operators for the Laplace equation in 2-D and 3-D based on structured matrix decompositions
Homework 10 Project Report: S, R, S|S, S|R , R|R operator evaluation
11/18/03 Lecture 21* General theory of diagonal forms for the FMM
for viewing
Lecture 22 Theory of the adaptive FMM
for viewing
Lecture 23 Adaptive FMM from Cheng et al (1999)
Connection between the FMM and Boundary Element Methods
12/02/03 Lecture 24 Some research ideas/directions. Review
12/04/03 Project Reports 1 1. Yang Wang: A Java-based animated implementation of the FMM in 2-D
2. Zhenyu Zhang: FMM for the solution of an eigenvalue problem for a surface integral operator in 3-D
3. Karthikeyan Duraisamy: Fast particle methods for the simulation and control of 3D Vortex Wakes from Lifting Wakes
Zhiyun Li: Nonuniform Fast Fourier Transforms
12/09/03 Project Reports 2 5. Weigong Zhang: Fast summation of Helmholtz monopoles in 2-D.
6.  Alap Karapurkar:
The Fast Multipole Method for Diffuse Light Scattering
7. Shaju John and S. Koushik:
Simulation of ferromagnetic particle chain formation in a fluid medium under the action of a magnetic field
8: Shreyas Ananthan and Sandeep Gupta: Fast Multipole Methods for Particle Simulations in Vortex Dominated Flows

All project final reports are due on this day.

12/11/03 Final Solution


* These lectures have been distributed as hardcopy, since they are based on as yet unpublished research.