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
E-mail: 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 1-D functions The 1-D 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, Far-field 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, S|R 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.