Fast Multipole Methods represent an area of vigorous research at UMIACS. The effort is lead by Nail Gumerov and Ramani Duraiswami with several students, visitors and collaborators. In this page an overview of this research is provided.
NEW: See our book Fast Multipole Methods for the Helmholtz Equation in Three Dimensions (The Elsevier Electromagnetism Series)
Background
The fast multipole method has been called one of the ten most significant algorithms in scientific computation discovered in the 20th century (along with algorithms such as the FFT), and won its inventors, Vladimir Rokhlin & Leslie Greengard, the 2001 Steele prize, in addition to getting Greengard the ACM 1987 best dissertation award.
The algorithm allows the product of particular dense matrices with a vector to be evaluated approximately (to a specified precision) in O(Nlog N) operations, when direct multiplication requires O(N2) operations. These matrices are those whose elements arise from distributions of points {x} and {y} in Rd, i.e. each element of the matrix can be represented as
Aij=j(xi,yj).
Coupled with advances in iterative methods for the solution of linear systems, they provide O(N log N) time and memory complexity solutions of problems that hitherto required O(N3) or O(N2) time complexity and O(N2) memory complexity. For extremely large problems, the gain in efficiency and memory can be very significant.
FMM work
Our work on the FMM has focused on both generalizing the method so that it can be applied as a general matrix-vector acceleration algorithm and applying it to many different problem areas. We have also focused on extending the method to new problem areas, especially in statistics and vision. We have also developed what perhaps the first course offered on the FMM anywhere. Our class notes for the most current course are here and links to older course notes are also provided.
Links to some papers are presented below.
-
Nail A. Gumerov, Ramani Duraiswami, “A scalar potential formulation and translation theory for the time-harmonic Maxwell equations,” Department of Computer Science Technical Reports CS-TR-4785, Institute for Advanced Computer Studies, UMIACS-2006-09. pdf (accepted Journal of Computational Physics)
-
Vikas C. Raykar, Ramani Duraiswami, “Very fast optimal bandwidth selection for univariate kernel density estimation,” Department of Computer Science Technical Report CS-TR-4774, UMIACS Technical Report UMIACS-TR-2005-73. pdf
(a shortened and edited version appears in the Proceedings Sixth SIAM International Conference on Data Mining, April 2006 ) -
Nail A. Gumerov and Ramani Duraiswami. Fast radial basis function interpolation via preconditioned Krylov iteration. accepted SIAM J. Scientific Computing, 2006. pdf matlab
-
Nail A. Gumerov and Ramani Duraiswami. FMM accelerated BEM for 3D Laplace & Helmholtz equations. Proceedings International Conference on Boundary Element Techniques, Paris, 2006. pdf
-
Ramani Duraiswami and Nail A. Gumerov, Iterative methods for use with the fast multipole method. In Abstracts of the Ninth Copper Mountain Conference on Iterative Methods, Apr 2006. Talk
-
Ramani Duraiswami, Dmitry N. Zotkin, and Nail A. Gumerov. Fast evaluation of the room transfer
function using multipole expansion. IEEE Transactions on Speech and Audio Processing, Accepted,
to appear, Jan 2007. pdf -
Nail A Gumerov and Ramani Duraiswami, Fast Multipole Methods for the Helmholtz Equation in Three Dimensions (The Elsevier Electromagnetism Series) Hardcover: 426 pages, Publisher: Elsevier Science (March 15, 2005), ISBN: 0080443710
-
Nail A. Gumerov and Ramani Duraiswami, Computation of scattering from clusters of spheres using the fast multipole method, J. Acoust. Soc. Am.. 117 (4), Pt. 1, April 2005, pp. 1744-1761 pdf
-
Nail A. Gumerov and Ramani Duraiswami, "Comparison of the efficiency of translation operators used in the fast multipole method for the 3D Laplace equation," University of Maryland, Department of Computer Science Technical Report CS-TR-4701 (Institute for Advanced Computer Studies Technical Report UMIACS 2005-09) pdf
-
Changjiang Yang, Ramani Duraiswami and Larry S. Davis A Robust and Efficient Kernel-Based Similarity Measure with Application to Object Tracking, IEEE Conference on Computer Vision and Pattern Recognition, San Diego, 2005 pdf
-
Vikas C. Raykar and Ramani Duraiswami, “The improved fast Gauss transform with applications to machine learning,” NIPS 2005 Workshop on Large Scale Kernel Machines, Whister, BC. Organized by Léon Bottou, Olivier Chapelle, Dennis Decoste, Jason Weston,
Slides -
Fast Multipole Method Based Filtering of Nonuniformly Sampled Data. Nail A. Gumerov, Ramani Duraiswami, unpublished, pdf
- Nail A. Gumerov and Ramani Duraiswami. “Recursions for the computation of multipole translation and rotation coefficients for the 3-D Helmholtz equation,” SIAM J. Sci. Stat. Comput. pdf
Meeting:
A highly topical meeting
on the fast multipole method and related algorithms was held at the Center for
Scientific Computation and Applied Mathematical Modeling at the
Current Students:
- Zhenyu Zhang
- Vikas Raykar
- Adam O' Donovan
Former Students
- Ahmed Elgammal
-
- Changjiang Yang
In addition the students in our class have done interesting projects on aspects of the FMM.
Other FMM collaborators
- Isaak Mayergoyz
- Dmitry N. Zotkin
- Fad Seydou
- Howard Elman
- Ahmed Elgammal
Courses
- Seven Tutorial Lectures on the FMM, given at CSCAMM FAM04 pdf
- CMSC 878R/AMSC 698R notes and assignments are here.
Ph.D. Thesis
Zhihui Tang, Fast Transforms Based on Structured Matrices with Applications to the Fast Multipole Method, 2003. pdf (Several ideas were explored for speeding up translation operators. the methods that resulted were not too promising. The main results were variants of fast algorithms for Pascal matrices)
Talks