[ Search | Site Map | Contact ]

Center for Scientific Computation and Mathematical Modeling

Research Activities > Programs > Fast Approximate Algorithms

Fast Multipole Method, Tree-Code and Related Approximate Algorithms.
Trading Exactness for Efficiency.

CSCAMM Program Spring 2004

Dates: April 19-30, 2004

CSIC Building (#406), Seminar Room 4122.
Directions: home.cscamm.umd.edu/directions

Program Overview
Week 1
04/19 - 04/22:
[Speakers] [Schedule] [Tutorials]
Week 2
04/26 - 04/30:
Workshop on Trading Exactness for Efficiency
[Focal Points] [Invited Participants] [Schedule] [Lectures]

Quick Navigator
Scientific Background Goals Scientific Content
Focal Points Organizing Committee Acknowledgement
Funding Invited Participants Poster & Photos


Due to space limitations, please register/RSVP at /programs/fam04/rsvp.htm

(Due to the large number of applications for the workshop on Trading Exactness for Efficiency (April 26-30), we regret that RSVP is now closed to new applicants of the second workshop)


A two-week program on the Fast Multipole Method (FMM), Tree-code and related algorithms will be conducted at the newly established Center for Scientific Computation And Mathematical Modeling (CSCAMM) at the University of Maryland, College Park.

The FMM algorithm allows the O(N2) matrix-vector product of particular dense matrices to be evaluated approximately -- up to a specified precision, in O(N) or O(Nlog N) operations. Coupled with advances in iterative methods for the solution of linear systems, the gain in efficiency and memory achieved by these algorithms can be very significant, and enable the use of more sophisticated modeling approaches that, while known to be better, may have been discarded as computationally infeasible in the past.

FMM and Tree-code algorithms have been developed for astrophysical many-body problems, for bio-molecular force-field computations, for solution of the Laplace and Poisson equations in applications such as fluid mechanics, for the solution of acoustical scattering (the Helmholtz equation), and electromagnetic scattering (Maxwell’s equations).

FMM algorithms have also been developed for the solution of interpolation problems in one to four dimensions, for performing non uniform Fourier transforms, for performing fast summations of Gaussians and of other radial-basis functions.

The O(NlogN) Tree-code has meant big improvements in simulation (disk) galaxies especially when special geometries cannot be taken advantage of. Multipole expansions combined with treecode enable O(N) codes, which in turn meant larger number of particles can be achieved, which is essential to resolve the 3D structure of flat galaxies, especially in the case of interactions.

Back to Top


With such an impressive breadth of applications, there is a need for for a focused activity of the widely-spread research community on algorithmic details and the translation of results from one application area to another. One of the goals of this two-weeks workshop is to provide a forum for such an exchange.

Another goal is to address common difficulties and raise open questions drawn from the various research communities. These include but are not limited to development of efficient translation operators, development of data-structures for efficient implementation, establishing optimal versions of the algorithms, extensions to higher dimensions, new application areas, and more.

Finally, the aim is to establish connections with related areas of scientific computation and applied mathematics. These include developing efficient O(N) preconditioners (suitable for use with the FMM), other algorithms that trade exactness for complexity, the non-uniform fast fourier transform, multiresolution methods and others.


Week 1 - Tutorials (April 19-22)

The first week will be devoted to hands-on tutorial of the Fast Multipole Method and its applications. These lectures, at the graduate level, will provide an introduction to the method and its details, and should allow the participant to understand the method fully, and begin using it in her/his research.


Nail Gumerov and Ramani Duraiswami (University of Maryland)
Fast Multipole Methods: Fundamentals and Applications [Introduction PDF]
  1. An Introduction to the Fast Multipole Method
  2. Key Ideas in the Fast Multipole Method
  3. Representations and Translations of Functions in Fast Multipole Methods
  4. Data Structures for the FMM
  5. Multilevel FMM Algorithm
  6. FMM for the Solution of Laplace’s Equation
  7. FMM for the Solution of Helmholtz’ Equation

Dennis Healy (University of Maryland)
Fast Multipole Methods: A Survey

Peter Teuben (University of Maryland)
NEMO Stellar Dynamics Toolbox Hands-on
  1. Introduction to NEMO
  2. NEMO Integrators
  3. Programming in NEMO


Click Here for Tutorial Schedule

Week 2 - Workshop on Trading Exactness for Efficiency (April 26-30)
(Due to the large number of applications for this workshop, we regret that RSVP is now closed to new applicants)


The workshop will be devoted to a research symposium with the goal of trying to elucidate the research directions being taken by various groups. There will be talks by a select group of invited participants. A goal of this second workshop will be the publication of a set of papers based on these talks.

Back to Top


  • Approximation & complexity
  • Non-uniform based wavelets
  • Hierarchically based FMM
  • Tree-code - theory and applications
  • Computations in biological applications, acoustics, EM, Statistics
  • Many body problems - from molecular level to cosmology applications


Click Here for Workshop Schedule

Back to Top





Ramani Duraiswami UMIACS, Univ. of Maryland
Bjorn Engquist PACM, Princeton University
Dennis Healy Math, Univ. of Maryland and DARPA
Eitan Tadmor CSCAMM, Math and IPST, Univ. of Maryland
Peter Teuben Astronomy, Univ. of Maryland


Partial funding is provided by the Princeton Institute for Computational Science and Engineering (PICSiE). Additional support is provided by the University of Maryland Institute for Advanced Computer Studies (UMIACS).


A limited amount of funding for participants at all levels is available, especially for researchers in the early stages of their career who want to attend the full program.




University of Colorado at Boulder
John Hopkins University
University of Illinois
Yale University
University of Leicester, UK
University of Maryland
Princeton University
Carnegie Mellon University
Courant Institute - NYU
University of Bonn
University of Maryland
University of Maryland
University of Toyko
University of Michigan
Duke University
University of Illinois
University of Maryland
University of Maryland
Yale University
University of Maryland
University of Maryland
Princeton University
HRL Laboratories

Back to Top