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 AT umiacs.umd.edu; gumerov AT umiacs.umd.edu

class email: cmsc878r AT umiacs.umd.edu

 

Fall 2002, Tuesdays and Thursdays, 12:30 p.m. – 1:45 p.m.,

Location: CSI 3118

 

Course Outline

Send class email

Lecture Notes

(Note: 03/10/2005 : 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/03/2002  

Lecture 1

Introduction

Applications: Physics, Computer Vision, etc.

Simple example of factorization for degenerate kernel

09/05/2002

Lecture 2

FMM in General Terms.

Review of Publications.

Asymptotic Complexity. Examples of complexity

Homework 1

Solution

Simple factorization example.

Intro to Matlab.

09/10/2002

Lecture 3

Factorization.

Local expansions. Far and local expansions.

Taylor series. Power series. Taylor series. Error bounds.

09/12/2002

Lecture 4

Multidimensional Taylor series.

Kronecker product. Dot product.

General form of factorization.

Properties of Kronecker and dot product.

Homework 2

Solution

Middleman factorization for sums of Gaussians using Taylor series.

09/17/2002

Lecture 5

Compression of multidimensional series.

Compression operator. Complexity in d-dimensions.

Use of compression in multidimensional FMM.

09/19/2002

Lecture 6

Far field expansions.

Functional analysis review.

Basis functions. Far field expansions.

Examples of far field expansions (power, asymptotic)

Homework 3

Solution

Multidimensional middleman for FGT and use of the “Compression” operator.

09/24/2002

Lecture 7

Operators in space of coefficients.

Truncation operators.

Translation operators.

Operator norms. Errors.

S|S, R|R, S|R operators

09/26/2002

Lecture 8

Single level FMM

Requirements for functions in FMM. SLFMM.

Formalization of FMM. SLFMM and optimization.

Homework 4

Solution

S|R translation operator for (x-y)-1. Error bounds.

10/01/2002

Lecture 9

Data Structures. 2d-trees.

Need for data structures.

2d trees. Parents, children, etc.

Hierarchical space subdivision.

10/03/2002

Lecture 10

Data Structures. Bit interleaving and spatial ordering.

Neighbor search.

Threshold level of space subdivision.

Homework5

Solution

Single Level FMM for (x-y)-1. Error bounds

10/08/2002

Lecture 11

Multilevel FMM.

Structure of the algorithm.

Setting data structure.

Upward Pass.

Hierarchical domains and potentials.

Upward Pass.

10/10/2002

Lecture 12

Multilevel FMM.

Downward Pass.

Asymptotic Complexity of the MLFMM.

Downward Pass. Complexity of each step.

Homework6

Solution code

Bookkeeping routines necessary for MLFMM based on bit-interleaving

10/15/2002

Lecture 13

Multilevel FMM.

Optimization.

Results of MLFMM tests.

Dependence of FMM performance on parameters.

Exam 1

Solution

Review of concepts.

10/22/2002

Lecture 14

Adaptive multilevel FMM.

Data structures.

D-trees and C-forests.

Adaptive MLFMM algorithm.

10/24/2002

Lecture 15

Discussion of multilevel FMMs

Data structures and elements of the algorithms.

More insight into the MLFMM.

Neighborhoods and dimensionality.

10/29/2002

Lecture 16

Methods for solution of linear systems

Iterative methods (Conjugate gradient, Krylov, etc.)

Use of the FMM in iterative solvers.

10/31/2002

Lecture 17

Error bounds for the MLFMM.

A scheme to obtain the error bounds.

Error for sequences of translations.

Homework7

Solution

MLFMM for (x-y)-1 in 1-D

11/05/2002

Lecture 18

Error bounds for the MLFMM

Example problems (1 and 2 D).

Error bounds and optimization.

S|S,R|R, and S|R-translation errors.

Examples.

11/07/2002

Lecture 19

Some application of the MLFMM.

2D, 3D potential fields, particle simulations, RBF.

Complex potentials. Example problems.

11/12/2002

Lecture 20

3D problems and vector analysis.

Green functions. Green's identity.

Boundary element method.

Reduction of 3D problems to forms for FMM use.

Spherical Harmonics.

11/14/2002

Lecture 21

(Guest Lecturer: Prof. D. Healy)

Fast spherical transform and applications.

Spherical harmonics. Properties.

Algorithm. Introduction, examples, and computational results .

11/19/2002

Lecture 22

3D Laplace and Helmholtz equations.

Multipoles. Translation theory.

Recursive computations.

Rotation-coaxial translation decomposition.

Multipoles. Differentiation/recursion.

11/21/2002

Lecture 23

Research directions in the FMM.

Identification of problems and possible ways of their solution.

Scaling, adaptivity, etc.

11/26/2002

Lecture 24

Integral transforms and fast translations.

Integral transforms. Signature function.

Sparse matrix decomposition.

Examples for the 3D Helmholtz equation.

12/03/2002

Lecture 25

This review of the course

12/05/2002

Lecture 26

Guest-Lecture by Prof. Sharat Chandran on FMM for the radiosity kernel.

*CANCELLED DUE TO THE WEATHER*

12/10/2002

Lecture 27

Project reports : (See the report format pdf tex)

FMM for

·       Fast Gauss Transform in multiple dimensions (Changjiang Yang).

·      Fast vortex methods in 2D (Jun Shen).

·      Thin plate splines in 2D (Ali Zandifar, Ser Nam Lin).

·       Vortex methods in 3D (J. Sitaraman).

·       Multiquadrics in 3D (Kexue Liu).

·       Conformal mapping using the S-C transform (Hazem El-Alfy).

·       kernel methods in statistical learning (Vikas Raykar, Ankur).

·       Inverse electromagnetics in 2D (Fad Seydou)

12/12/2002

Final

Solution