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/2011Lecture 4Expansions of entagled functions via Taylor series, asymptotic methods


09/15/2011Lecture 5

Homework 2
Expansions of the Green's function of Laplace and Helmholtz equation Green's functions in 2D and 3D


09/20/2011Lecture 6
Well separated sets. Organizing factorizations. The preFMM algorithms

Callahan and Kosaraju, WSPD (1995)
09/22/2011Lecture 7

Homeworks 3 + 4
Function representations in bases. Translation Operators


09/27/2011Lecture 8
Single Level FMM


09/29/2011Lecture 9
Multi Level FMM


10/04/2011Lecture 10
Review of the FMM Algorithm

Demo of the FMM algorithm
10/6/2011Lecture 11

Homework 5

Introduction to Iterative methods

Y. Saad books
10/11/2011Lecture 12
Fast Gauss Transform and improvements

Greengard & Strain;       Yang et al.;
 Raykar et al;          Morariu et al.
10/13/2011Lecture 13-14

Homework 6
Data Structures for the FMM

Gumerov et al.
10/18/2011See 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/2011Lecture 18
Adaptive FMM algorithms

Cheng et al. (1999)            
11/8/2011Lecture 19
Radial Basis Function Interpolation

Faul et al. (2005)     Gumerov & Duraiswami (2007)
11/10/2011Lecture 20
Fast Multipole Methods on Graphics Processors

11/15/2011Lecture 21
Prof. David Mount Guest Lecture on Nearest Neighbors


11/17/2011Lecture 22
No Class
Project Updates Due
11/22/2011Lecture 23
Non Uniform FFT
Dutt and Rokhlin

11/24/2011
Thanksgiving


11/29/2011Lecture 24
Polyharmonic, Stokes and Maxwell Kernels
G&D (2006)   G&D (2007)
12/1/2011Lecture 25
Kernel Independent FMM

Ying et al. (2004)
12/6/2011Lecture 26
Review


12/8/2011Lecture 27
Project Presentation
Yuancheng Luo; Ross Adelman;  Abhishek Kumar
12/13/2011Lecture 28Project 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)