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
http://www.umiacs.umd.edu/~ramani/cmsc878R/outline.html
E-mail: ramani@umiacs.umd.edu; gumerov@umiacs.umd.edu
class email: cmsc878r AT umiacs.umd.edu
Fall 2003, Tuesdays and Thursdays, 3:30 p.m. – 4:45 p.m.,
Homework is given on Thursdays at the end of the class
and due on the next
Tuesday at the beginning of class
Send class email
Lecture Notes
(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 |
|
09/02/2003 for viewing
for
printing
|
Lecture 1 |
Introduction, Course rules, exams
Applications: Physics, Computer Vision, etc.
Simple example of factorization for degenerate kernel Asymptotic Complexity. Examples of complexity
Review of Publications.
|
|
09/04/2003 for viewing for printing
|
Lecture 2
|
Review of the factorization idea Structured Matrices Integral Equations
Fast Fourier Transform
|
|
Simple factorization example.
Intro to Matlab.
|
||
|
09/09/2003 for viewing for printing |
Lecture 3
|
Factorization Regular and Singular Expansions. Taylor Series, Error Analysis. |
|
09/11/2003 for viewing for printing |
Lecture 4
|
Series expansions for factorization Kronecker products Compression of series |
| Homework 2 | Solution | Fast Gauss transform based on Taylor Series |
|
09/16/2003 for viewing for printing |
Lecture 5
|
Near/Far Singular/Regular Expansions Example of S and R expansions of a singular function Error bounds |
| 09/18/2003 |
Lecture 6
|
Class canceled due to Hurricane Isabel |
|
09/23/2003 for viewing for printing |
Lecture 6 |
Splitting of the FMM sum Spatial ordering The Pre-FMM algortithm using R expansions and S expansions Optimization of the number of boxes in the Pre-FMM Complexity of the Pre-FMM |
|
09/25/2003 for viewing for printing |
Lecture 7 | Introduction to translation operators |
| Homework 3/4 | Solution | Implementation of Data Structures for 1-D Pre-FMM |
|
09/30/2003 for viewing for printing |
Lecture 8 | (based on notes of previous lecture) |
|
10/02/2003 for viewing for printing |
Lecture 9 | Single Level FMM (SLFMM) |
|
10/07/2003 for viewing for printing |
Lecture 10 | Review |
|
10/09/2003 for viewing for printing |
Lecture 11 | Multilevel FMM |
| Homework 5 | Solution | S, R and S|R translation in one dimension. Error bounds |
|
10/14/2003 for viewing for printing |
Lecture 12 | Hierarchical Data Structures for space sub-division |
|
10/16/2003 for viewing for printing |
Lecture 13 | Hierarchical Data Structures for space sub-division |
| Homework 6 | Solution | |
|
10/21/2003 for viewing for printing |
Lecture 14 | Bit interleaving and deinterleaving |
| 10/23/2003 | Mid Term Exam | Solution |
| Homework 7 | Solution | Data Structures |
|
10/28/03 for viewing for printing |
Lecture 15 | Introduction to iterative methods for use with the FMM |
|
10/30/03 for viewing for printing |
Lecture 16 |
Review of Exam and previous class Complexity of MLFMM |
| Homework 8 | 1-D MLFMM | |
|
11/02/03 for viewing for printing |
Lecture 17 |
Review of MLFMM Error analysis of the MLFMM-I Project Info. |
|
11/04/03 for viewing for printing |
Lecture 18 |
Error analysis of the MLFMM-II |
| Homework 9 | Project Preliminary report (See Lecture 17) | |
|
11/11/03 for viewing |
Lecture 19 | FMM for the Gravitational/Coulombic potential. Introduction to Spherical Harmonics. |
| 11/13/03 | Lecture 20* | Guest Lecture by Zhihui Tang: Fast translation operators for the Laplace equation in 2-D and 3-D based on structured matrix decompositions |
| Homework 10 | Project Report: S, R, S|S, S|R , R|R operator evaluation | |
| 11/18/03 | Lecture 21* | General theory of diagonal forms for the FMM |
|
11/20/03 for viewing |
Lecture 22 | Theory of the adaptive FMM |
|
11/25/03 for viewing |
Lecture 23 |
Adaptive FMM from Cheng et al (1999) Connection between the FMM and Boundary Element Methods |
| 12/02/03 | Lecture 24 | Some research ideas/directions. Review |
| 12/04/03 | Project Reports 1 |
1. Yang Wang: A Java-based animated implementation of
the FMM in 2-D 2. Zhenyu Zhang: FMM for the solution of an eigenvalue problem for a surface integral operator in 3-D 3. Karthikeyan Duraisamy: Fast particle methods for the simulation and control of 3D Vortex Wakes from Lifting Wakes 4. Zhiyun Li: Nonuniform Fast Fourier Transforms |
| 12/09/03 | Project Reports 2 |
5. Weigong Zhang: Fast summation of Helmholtz monopoles
in 2-D. 6. Alap Karapurkar: The Fast Multipole Method for Diffuse Light Scattering 7. Shaju John and S. Koushik: Simulation of ferromagnetic particle chain formation in a fluid medium under the action of a magnetic field 8: Shreyas Ananthan and Sandeep Gupta: Fast Multipole Methods for Particle Simulations in Vortex Dominated Flows All project final reports are due on this day. |
| 12/11/03 | Final | Solution |
* These lectures have been distributed as hardcopy, since they are based on as yet unpublished research.