Fast Multipole Methods: Fundamentals and Applications
Instructors: Ramani Duraiswami & Nail A. Gumerov
Course No. CMSC 858M/AMSC 698R
Email: ramani AT
umiacs.umd.edu;
gumerov AT
umiacs.umd.edu
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
This course will involve a project – for maximum benefit you should start looking for a project early in the course.
DATE 
LECTURE 
CONTENTS 


09/01/2011 
Introduction, Course rules, exams Structure and Efficiency Algorithm Complexity and the solution of Large Problems Applications: Physics, Computer Vision, etc. Simple example 
G. Steele Prize
Announcements, 2001 

09/06/2011 

C. Moler (Chapter on the FFT) 

09/08/2011 
Lecture 3 Homework 1 
Factorization, Truncation, Error bounds "Middleman" method 

09/13/2011  Lecture 4  Expansions of entagled functions via Taylor series, asymptotic methods  
09/15/2011  Lecture 5 Homework 2  Expansions of the Green's function of Laplace and Helmholtz equation Green's functions in 2D and 3D  
09/20/2011  Lecture 6  Well separated sets. Organizing factorizations. The preFMM algorithms  Callahan and Kosaraju, WSPD (1995)  
09/22/2011  Lecture 7 Homeworks 3 + 4  Function representations in bases. Translation Operators  
09/27/2011  Lecture 8  Single Level FMM  
09/29/2011  Lecture 9  Multi Level FMM  
10/04/2011  Lecture 10  Review of the FMM Algorithm  Demo of the FMM algorithm  
10/6/2011  Lecture 11 Homework 5  Introduction to Iterative methods  Y. Saad books  
10/11/2011  Lecture 12  Fast Gauss Transform and improvements  Greengard & Strain; Yang et al.; Raykar et al; Morariu et al.  
10/13/2011  Lecture 1314 Homework 6  Data Structures for the FMM  Gumerov et al.  
10/18/2011  See above  Data Structures  
10/20/2011 
EXAM 
In Class 

10/25/2011  Lecture 15  FMM Error Analysis  Project Proposals Due  
10/27/2011  Lecture 16 Homework 7  Fast Translation Algorithms  
11/1/2011  Lecture 17  Boundary Element Methods and the FMM  
11/3/2011  Lecture 18  Adaptive FMM algorithms  Cheng et al. (1999)  
11/8/2011  Lecture 19  Radial Basis Function Interpolation  Faul et al. (2005) Gumerov & Duraiswami (2007)  
11/10/2011  Lecture 20  Fast Multipole Methods on Graphics Processors 
 
11/15/2011  Lecture 21  Prof. David Mount Guest Lecture on Nearest Neighbors  
11/17/2011  Lecture 22  No Class  Project Updates Due  
11/22/2011  Lecture 23  Non Uniform FFT  Dutt and Rokhlin  
11/24/2011  Thanksgiving  
11/29/2011  Lecture 24  Polyharmonic, Stokes and Maxwell Kernels  G&D (2006) G&D (2007)  
12/1/2011  Lecture 25  Kernel Independent FMM  Ying et al. (2004)  
12/6/2011  Lecture 26  Review  
12/8/2011  Lecture 27  Project Presentation  Yuancheng Luo; Ross Adelman; Abhishek Kumar  
12/13/2011  Lecture 28  Project Presentation  Bharath; GM BowenDavies; Tarandeep Kalra; 
Other References
L. Greengard and J.
Strain, "The
Fast Gauss Transform,"