Fast Multipole Methods: Fundamentals and Applications

Instructors: Ramani Duraiswami  & Nail A. Gumerov

Course No. CMSC 858M/AMSC 698R

E-mail: 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

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.

DATE	LECTURE	CONTENTS	READING
09/01/2011	Lecture1	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
09/06/2011	Lecture 2	Factorization Example; FFT, Complexity Notation	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 13-14 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 Bowen-Davies; Tarandeep Kalra;

Other References

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