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)



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


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.


  1. 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)

  2.  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 ) 

  3. Nail A. Gumerov  and Ramani Duraiswami. Fast radial basis function interpolation via preconditioned Krylov iteration. accepted SIAM J. Scientific Computing, 2006. pdf matlab

  4. Nail A. Gumerov and Ramani Duraiswami. FMM accelerated BEM for 3D Laplace & Helmholtz equations. Proceedings International Conference on Boundary Element Techniques, Paris, 2006.  pdf

  5. 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

  6. 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

  7. 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

  8. 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

  9. 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

  10. 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

  11. 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,

  12. Fast Multipole Method Based Filtering of Nonuniformly Sampled Data. Nail A. Gumerov, Ramani Duraiswami, unpublished, pdf

  13. 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
  14. Zhihui Tang, Ramani Duraiswami, Nail A. Gumerov.  Fast algorithms to compute matrix vector products for Pascal matrices. Also published as UMIACS-TR-2004-08, CS-TR-4563. pdf
  15. Zhenyu Zhang, Isaak D. Mayergoyz, Nail A. Gumerov and Ramani Duraiswami. Numerical Analysis of Plasmon Resonances in Nanoparticles Based on Fast Multipole Method, accepted to appear, IEEE Transactions on Magnetics, 2007, pdf




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 University of Maryland, College Park in April 2004. The first week of the meeting was a tutorial on the FMM.

Current Students:

  • Zhenyu Zhang
  • Vikas Raykar
  • Adam O' Donovan

Former Students

  • Ahmed Elgammal
  • Eugene Borovikov
  • 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



  • 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)



·         Fast Multipole Methods for Incompressible flow simulation, Ramani Duraiswami & Nail Gumerov,  Presented at the CSCAMM Workshop on Perspectives on Incompressible Flows, Abstract, Slides

·         Acoustical scattering from N spheres using a multilevel fast multipole method, Nail Gumerov & Ramani Duraiswami, Presented at the Acoustical Society of America meeting in Nashville, 2003.  Abstract, Slides

Open Source Software

·          The Improved Fast Gauss Transform. available under the LGPL from Vikas Raykar's site



Commercial Software

Some of our software is being further developed (under license from the University of Maryland) by a small business (Fantalgo, LLC).


Fast Multiple Method, Tree-Code and Related Approximate Algorithms.Trading Exactness for Efficiency. CSCAMM Program Spring 2004 (co-sponsored by UMIACS)


Work supported by NSF Awards 00860750219681, and internal UMIACS funds.

We welcome collaborations and joint projects/proposals with domain computational scientists seeking to employ the FMM to speed up calculations in their fields. We are also open to enquiries for consultation on any of this work, or on the FMM in general.