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
Email: ramani AT umiacs.umd.edu; gumerov AT umiacs.umd.edu
Fall 2004, Mondays and Thursdays, 12:30 p.m. – 1:45 p.m.,
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))
DATE 
LECTURE 
CONTENTS 
08/30/2004

Introduction, Course rules, exams
Applications: Physics, Computer Vision, etc.
Simple example of factorization for degenerate kernel Asymptotic Complexity. Examples of complexity 

09/01/2004 
Review of the factorization idea Structured Matrices Integral Equations
Fast Fourier Transform



Simple factorization example.


09/08/2004  Lecture 3 
Far and Near Fields Local Expansions and Domains of validity Factorization via Taylor Series for 1D functions The 1D 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, Farfield expansions, Validity Examples 
09/15/2004  Lecture 5 
Local and Singular expansions Factorization via regular and singular expansions: The "PreFMM" Complexity and optimizing the number of groups 
Homework3/4  
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, SR 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 
11/17/2004 
* These lectures have been distributed as hardcopy, since they are based on as yet unpublished research.