Dear editor of CiSE,
The article "The Fast Multipole Algorithm" (FMA) by John Board and
Klaus Schulten , which is one of the theme articles under the title
"The Top 10 Algorithms of the Century" (Jan/Feb 2000 issue of CiSE)
includes a number of incorrect and highly misleading statements.
First, the contention that "Rokhlin and Greengard arguably provided
the first numerically defensible method for reducing the N-body
problem's computational complexity" is seriously flawed. FMA appeared
about three years after its close relative, the Barnes-Hut tree
algorithm. Since both are based on the same mathematics (except that
the treecode is simpler), they are equally "numerically defensible".
Moreover, there are several methods other than FMA and the tree
algorithm, which reduce the complexity of N-body problem from O(N^2)
to something cheaper. Examples are the particle-mesh (PM) scheme, the
particle-particle particle-mesh (P3M) scheme, the direct Ewald method
and so on. All of these algorithms were known at least a decade
before the invention of FMA or the tree algorithm.
Other errors include
- the claim that "astrophysicists tends to gravitate to the former
solution" (attacking the O(N^2) complexity with brute force). PM and
P3M have been used in astrophysics for more than two decades, and the
tree algorithm was developed by astrophysists.
- the claim that special-purpose devices such as the GRAPE, Delft
machine, and Transputer machines can do only O(N^2) brute-force
calculations. GRAPE hardwares have been used with the tree algorithm
for many years, the Delft machine is designed for O(N) calculation of
short-range interactions, and the Transputer machine can handle any
algorithm that can be run on a distributed-memory parallel machine.
- the implication that tree algorithms only use the monopole and
dipole terms. Actually, almost every existing implementation of the
tree algorithm used in astrophysics includes at least the quadrupole
term, and some go higher if accuracy requirements warrant (which in
fact is rarely the case).
- the claim that the capability of handling non-1/r potentials is a
unique feature of FMA. Obviously the tree algorithm can do whatever
FMA can do, since both rely on multipole expansion. The PM and P3M
methods can also be adapted, if necessary.
- the claim that astrophysists use a "hybrid of the FMA and the
earlier Barnes-Hut scheme" is incorrect. To the best of my knowledge,
FMA has not been used in astrophysical calculations, simply because
the implementation is sufficiently complex and the potentially higher
accuracy rarely needed.
- the claim that Ewald summation method is newer than FMA. The
methods they referred as "fast versions of FMA" are actually just P3M
methods with high-order kernels, which one can find in standard
textbooks on particle simulation.
To summarize, I found the authors give a highly misleading historical
context and make inaccurate claims on the relative advantages of FMA
over other fast potential solvers. They are also rather unfair to FMA
itself, ignoring a wide range of new applications other than
particle-particle interactions (cf. the Sept/Oct 1998 issue of CiSE,
for recent developments in FMA on a variety of boundary value
problems). FMA is important and mathematically elegant, but it is not
the only game in town for particle methods, nor is it limited to those
applications.
With best regards,
Jun Makino
University of Tokyo