Fast Multipole Methods: Fundamentals and Applications
Instructors: Ramani Duraiswami & Nail A. Gumerov
Course No. CMSC 878R/AMSC 698R/MAIT 627
E-mail: ramani AT
umiacs.umd.edu;
gumerov AT
umiacs.umd.edu
Spring 2008, Tuesdays and Thursdays, 3:30 p.m. – 4: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 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.
The course outline below is a tentative organization of the material. It is
subject to change!
|
DATE |
LECTURE |
CONTENTS |
|
|
01/29/2008 |
Introduction, Course rules, exams Structure and Efficiency Algorithm Complexity and the solution of Large Problems Applications: Physics, Computer Vision, etc. |
·
G. · Steele Prize
Announcements, 2001 |
|
|
01/31/2008 |
Simple example of factorization for degenerate kernel Asymptotic Complexity. Examples of complexity Structured Matrices, Fast Fourier Transform |
C. Moler (Chapter on the FFT) |
|
|
(due 02/07/2008) |
Simple factorization example with a degenerate kernel. Remember to label axes in all plots. |
|
|
|
02/05/2008 |
Factorization of non
degenerate Kernels. Local and Far-field expansions. Examples. Taylor Series. |
D. Donoho,
"High-Dimensional
Data Analysis: The Curses and Blessings of Dimensionality," AMS
Lecture at a Conference on "Math
Challenges of the 21st Century" |
|
|
02/07/2008 |
|
|
|
|
|
Simple factorization example with a nondegenerate
kernel and truncated expansions with error bounds. Remember
to label axes in all plots. |
|
|
|
02/12/2008 |
Complexity of the “middleman” approach considering
errors. Grouping and exclusion to deal with non-factorizable
points. “Pre-FMM” algorithm with O(N3/2)
complexity. |
|
|
|
02/14/2008 |
|
Example of the (x-y)-1 kernel. Translation
operators. |
|
|
(due
02/21/2008) |
|
Pre-FMM … Introduces the grouping and factorization
ideas. Simple data structure for identifying points in a 1-D “box” via
sorting |
|
|
02/19/2008 |
|
|
|
|
02/21/2008 |
|
|
|
|
02/26/2008 |
Lecture 9 |
Demo based on code written by Yang Wang and Trung Nguyen as projects for the course |
You may need to download java from java |
|
02/28/2008 |
|
Complexity of the MLFMM |
|
|
03/04/2008 |
|
No class: Attend the following talk in MTH 3206 Professor Xiaobai Sun: Efficient Encoding of
Irregular Geometric Structures in Matrix Computations |
|
|
03/06/2008 |
|
Data Structures for the FMM |
|
|
03/11/2008 |
Lecture 12 (Click on previous lecture) |
Data Structures for the FMM |
|
|
|
Data Structures |
|
|
|
03/13/2008 |
Error bounds for the FMM |
|
|
|
03/18/2008 03/20/2008 |
Spring Break |
No Class |
|
|
03/25/2008 |
Iterative Methods Lecture 1: |
|
|
|
03/27/2008 |
|
|
|
|
04/01/2008 |
|
||
|
04/03/2008 |
Proj Report 1 |
Faster translation methods |
|
|
04/08/2008 |
IFGT |
|
|
|
04/10/2008 |
IFGT + BEM |
|
|
|
04/15/2008 |
Proj Report 2 |
Adaptive FMM + discussion of a second adaptive algorithm |
|
|
04/17/2008 |
|
|
|
|
04/22/2008 |
|
|
|
|
04/24/2008 |
|
|
|
|
04/29/2008 |
|
|
|
|
05/01/2008 |
Helmholtz equation |
|
|
|
05/03/2008 |
Some issues with the FMM |
|
|
|
05/08/2008 |
Non uniform FFT FFTM |
|
|
|
05/10/2008 |
Project Presentations |
|
|
|
|
|
|
|
|
05/21/2008 Wednesday |
Final Exam |
10:30am-12:30 pm
(according to Testudo) Project Reports due |
|
Other References
L. Greengard and J.
Strain, "The
Fast Gauss Transform,"