Fast Multipole Methods: Fundamentals and Applications


Instructors: Ramani Duraiswami  & Nail A. Gumerov

Course No. CMSC 858M/AMSC 698R

E-mail: ramani AT;

gumerov AT

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

Location: CSI 3120


Questions/forums etc. via Piazza

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

Lecture Notes from previous years 2008 2006 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))

This course will involve a project – for maximum benefit you should start looking for a project early in the course.








Introduction, Course rules, exams

Structure and Efficiency

Algorithm Complexity and the solution of Large Problems

Applications: Physics, Computer Vision, etc.

Simple example

G. Moore, "Cramming More Components onto integrated circuits," Electronics, 38, 1965

Steele Prize Announcements, 2001

Dongarra and Sullivan, 2000


Lecture 2

Factorization Example; FFT, Complexity Notation

C. Moler (Chapter on the FFT)

Lecture 3

Homework 1
Factorization, Truncation, Error bounds
"Middleman" method

09/13/2011Lecture 4Expansions of entagled functions via Taylor series, asymptotic methods

09/15/2011Lecture 5

Homework 2
Expansions of the Green's function of Laplace and Helmholtz equation Green's functions in 2D and 3D

09/20/2011Lecture 6
Well separated sets. Organizing factorizations. The preFMM algorithms

Callahan and Kosaraju, WSPD (1995)
09/22/2011Lecture 7

Homeworks 3 + 4
Function representations in bases. Translation Operators

09/27/2011Lecture 8
Single Level FMM

09/29/2011Lecture 9
Multi Level FMM

10/04/2011Lecture 10
Review of the FMM Algorithm

Demo of the FMM algorithm
10/6/2011Lecture 11

Homework 5

Introduction to Iterative methods

Y. Saad books
10/11/2011Lecture 12
Fast Gauss Transform and improvements

Greengard & Strain;       Yang et al.;
 Raykar et al;          Morariu et al.
10/13/2011Lecture 13-14

Homework 6
Data Structures for the FMM

Gumerov et al.
10/18/2011See above
Data Structures

In Class

Lecture 15
FMM Error Analysis

Project Proposals Due
Lecture 16

Homework 7
Fast Translation Algorithms

Lecture 17
Boundary Element Methods and the FMM

11/3/2011Lecture 18
Adaptive FMM algorithms

Cheng et al. (1999)            
11/8/2011Lecture 19
Radial Basis Function Interpolation

Faul et al. (2005)     Gumerov & Duraiswami (2007)
11/10/2011Lecture 20
Fast Multipole Methods on Graphics Processors

11/15/2011Lecture 21
Prof. David Mount Guest Lecture on Nearest Neighbors

11/17/2011Lecture 22
No Class
Project Updates Due
11/22/2011Lecture 23
Non Uniform FFT
Dutt and Rokhlin


11/29/2011Lecture 24
Polyharmonic, Stokes and Maxwell Kernels
G&D (2006)   G&D (2007)
12/1/2011Lecture 25
Kernel Independent FMM

Ying et al. (2004)
12/6/2011Lecture 26

12/8/2011Lecture 27
Project Presentation
Yuancheng Luo; Ross Adelman;  Abhishek Kumar
12/13/2011Lecture 28Project Presentation
Bharath;  GM Bowen-Davies; Tarandeep Kalra;


Other References


L. Greengard and J. Strain, "The Fast Gauss Transform," SIAM J. Sci. and Stat. Comput. 12, 79 (1991)