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

  1. 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.
  2. 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.
  3. 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).
  4. 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.
  5. 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.
  6. 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