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