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

E-mail: ramani AT; gumerov AT


Fall 2004, Mondays and Thursdays, 12:30 p.m. 1: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 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))






Lecture 1

Introduction, Course rules, exams

Applications: Physics, Computer Vision, etc.

Simple example of factorization for degenerate kernel

Asymptotic Complexity. Examples of complexity


Lecture 2

Review of the factorization idea

Structured Matrices

Integral Equations

Fast Fourier Transform

Homework 1


Simple factorization example.


09/08/2004 Lecture 3 Far and Near Fields
Local Expansions and Domains of validity
Factorization via Taylor Series for 1-D functions
The 1-D fast Gauss transform
Factorization for multidimensional functions via Taylor series
Kronecker product notation
Homework 2   Fast Gauss Transform
09/13/2004 Lecture 4 Tensor product basis and reduction in complexity via multinomial coefficients
Singular Mother functions, Far-field expansions, Validity
09/15/2004 Lecture 5 Local and Singular expansions
Factorization via regular and singular expansions: The "PreFMM"
Complexity and optimizing the number of groups
09/20/2004 Lecture 6 Translation of expansions. Translation operators
09/22/2004 Lecture 7 Translations.
The Single Level Fast Multipole Method. Complexity
09/27/2004 Lecture 8 Multi Level FMM
09/29/2004 Lecture 9  
Homework 5   S expansions, R expansions, S|R translation
10/04/2004 Lecture 10 Data Structures for the FMM
10/06/2004 Lecture 11 Data Structures for the FMM
10/11/2004 Lecture 12 Fast Gauss Transform (guest lecture by Changjiang Yang)
10/13/2004 Lecture 13 Iterative Methods for Linear Systems
Homework 6   Data Structures
10/18/2004 Lecture 14 Error Analysis of the MLFMM (Theory)
10/20/2004 Lecture 15 Error Analysis of the MLFMM (worked out example)
10/25/2004 Lecture 16 Exam
10/27/2004 Lecture 17 Diagonal forms
11/.01/2004 Lecture 18 Adaptive Methods
11/03/2004 Lecture 19 Adaptive Methods (includes Lecture 18)
11/08/2004 Lecture 20 Multipoles and the Laplace Equation
11/10/2004 Lecture 21 Non Uniform FFT
11/15/2004 Lecture 22 Boundary Element Methods


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