Course Outline:

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

IF YOU HAVE PROBLEMS REGISTERING, COME TO CLASS ON 09/03/02 (TUESDAY) AND WE WILL FIGURE OUT WHAT TO DO

 

http://www.umiacs.umd.edu/~ramani/cmsc878R/outline.html

E-mail: ramani@umiacs.umd.edu; gumerov@umiacs.umd.edu

 

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

Location: CSI 3118

 

This course will introduce you to the fast multipole method, a numerical algorithm that is extremely promising for achieving fast solutions of many applied problems in science, engineering, biology, computer vision and statistics.

 

The course is directed at beginning graduate students who have had an introductory numerical analysis course, and have some knowledge of linear algebra.

 

The fast multipole method has been called one of the ten most significant numerical algorithms discovered in the 20^th century, and won its inventors, Vladimir Rokhlin and Leslie Greengard, the Steele prize. The algorithm allows the product of particular dense matrices with a vector to be evaluated in O(N logN) operations, when  direct multiplication requires O(N²) operations. Coupled with advances in iterative methods for solution of linear systems, they allow O(N logN)  time complexity and O(N) memory complexity solution of problems that hitherto required O(N³) time complexity and O(N²) memory complexity.

 

Despite these advantages, the FMM is not widely used, or efficiently employed.  This is primarily because implementing it requires an interdisciplinary set of skills. This course will provide you with the broad introduction necessary. There are many opportunities for research using the material to be taught --- both for applied scientists to develop efficient algorithms for problems in different fields, and for applied mathematicians to develop the theory for the algorithm and establish its performance.

 

The audience for the course is anyone doing numerical computation work in computer science, engineering, mathematics, statistics or any other field.

 

Administrativia

The course will include homework most weeks. Homework may require programming in one of either Matlab or a programming language of your choice (C/C++ or Fortran 90). The homework will account for 50% of the grade. No late homework submissions.

 

There will be a final project that will require you to implement an FMM algorithm in a field of your choice, and this will account for 20% of the grade. There will also be an intermediate exam worth 10%, and a final exam worth 20%.

 

There is no textbook. Lecture notes prepared by the instructors will be made available. There will also be readings from published papers.

 

There is the possibility of students being offered NSF supported Ph.D. assistantships at the end of the course.

 

Tentative Organization of the Course

 

Week 1. Introduction.

• What are multipole methods and what is this course about.
• Problems from physics, mathematics, computer vision, statistics, etc. that can be solved with multipole methods.
• Historical review of the fast multipole method.
• Review of Complexity
• Homework.

 

Week 2. Factorization.

• Taylor series.
• Basis functions. Examples.
• Expansions over the basis functions. Local and far-field expansions.
• Review of convergence of series
• Truncation errors.
• Homework.

 

Week 3. Operations with functions and expansion coefficients.

• Linear spaces of functions and expansion coefficients.
• Linear operators.
• Representations of linear operators in the space of coefficients.
• Translation operators.
• Truncation operators.
• Homework.

 

Week 4. Spatial grouping.

• The simplest fast multipole method --- the "Middleman" method.
• The need for spatial grouping.
• Non-hierarchical space subdivision. Single-level FMM.
• Example problems.
• Homework.

 

Week 5. Data structures for hierarchical spatial subdivision using 2^d-trees.

• Quadtrees, Oct-trees and 2^d-trees.
• Representations via Bit Interleaving: Spatial ordering.  Examples.
• Fast neighbor search and other algorithms.
• Hierarchical data structures.
• Homework.

 

Week 6. Non-adaptive multilevel FMM.

• Formal definition of problems that can be solved with multilevel FMM.
• Examples. Matrix-vector multiplication.
• Hierarchical spatial domains.
• Multilevel FMM algorithm.
• Homework.

 

Week 7. Adaptive multilevel FMM.

• Objective of the FMM.
• Setting hierarchical data structures.
• Construction of trees.
• Adaptive multilevel FMM.
• Homework.

 

Week 8. Computational complexity of the FMM.

• The fastest possible method.
• Asymptotic complexity of single-level FMM.
• Asymptotic complexity of multilevel FMM.
• Optimization of parameters for multilevel FMM. Non-adaptive and adaptive schemes.
• Homework.

 

Week 9. Potential Theory

• Physical basis. Potential fields. Green’s function.
• Multipole expansion of Green’s function.
• Green’s identity.
• Boundary value problems. Algorithms for solution.
• Review of iterative methods for the solution of linear systems.
• Homework.

 

Week 10. Translation of multipoles.

• Differentiation of multipoles.
• Reexpansions of multipoles.
• Recursive computation of the translation operators.
• Properties of translation operators.
• Homework.

 

Week 11. Laplace and Helmholtz equations in 2 dimensions.

• Elementary solutions for the Laplace equation.
• Elementary solutions for the Helmholtz equation.
• Integral representations of translation operators.
• Matrix representations of translation operators.
• Error bounds for translation operators.

 

Week 12. Laplace and Helmholtz equations in 3 dimensions (1).

• Elementary solutions in spherical coordinates.
• Spherical harmonics and their properties.
• Differentiation of elementary solution.
• Reexpansion of elementary solutions.
• Translation operators.
• Far-field signature function.
• Error bounds for translation operators.

 

Week 13. Laplace and Helmholtz equations in 3 dimensions (2).

• Rotation of spherical harmonics.
• Fast spherical harmonics transforms
• Recursive computation of rotation operators.

• Rotation-coaxial translation decomposition.
• Matrix representation of differential operators.
• Sparse matrix decomposition of translation operators.

 

 

Project topics

Fast multipole applications to these or other problems of interest to the student or his/her advisor

• image segmentation
• solution of acoustical wave scattering problems
• electromagnetic wave scattering
• implicit fitting of surfaces for graphics
• computational magnetics
• potential flow
• …