Dear George,
I read the article on FMM by Jon Board and Klaus Schulten which appeared on Jan/Feb issue of CiSE. I found it is full of incorrect statements, in particular when it deals with the historical context.
First of all, the statement "Rokhlin and Greengard arguably provided the first ... ", which is also used as the headline, is grossly incorrect. Even within the context of the FMM and tree-based schemes, they are the LAST to propose the method. As correctly mentioned in the article, both Appel and Barnes & Hut published their methods earlier than Rokhlin and Greengard did, and their methods are not, in any sense, less "numerically defensible" than that of Rokhlin and Greengard. Note that the first method proposed by Rokhlin and Greengard was not even adaptive, and therefore had very limited use.
Moreover, there are a number of methods other than the FMM and the tree algorithm, which reduces the complexity of N-body problem from O(N2) to something else, like the usual particle-mesh scheme, particle-particle particle-mesh scheme, direct Ewald method and so on. Thus, the "Historical context" they gave looks like their illusion.
They pushed their illusion even further, by stating " ... either attack the O(N2) complexity of the problem with brute force or ... Astrophysists tended to gravitate to the former solution." This is completely wrong. Astrophysists have been using PM, P3M, and Ewald method for a number of years, and tree algorithms have been developed mainly by astrophysists.
Of course, GRAPE's strength is in its capability to handle particle-particle interaction fast. However, that fact does not prevent its use in combination with tree method or FMM, as I and Makoto described in detail in our book, which they cited (They misspelled Makoto's name in the reference, which seems to indicate the amount of attention they paid to our book). Which method is to be used depends on a number of factors, such as required accuracy, the actual number of particles used, the spacial distribution of particles and the variation in the timescale.
The discussion on special-purpose machines for Molecular Dynamics calculation was also incorrect in many points. For example, neither Bakker's DMDP (They again misspelled his name) nor the Transputer machine by Boehncke handled Coulomb force by O(N2) brute force approach. DMDP was designed to handle any pairwise interaction with its programmable lookup table and interpolator. The transputer machine can handle any interaction, since it is an general-purpose programmable computer. Moreover, DMDP implemented the so-called linked-list method, which reduce the calculation cost of short-range interactions from O(N2) to O(N).
The section titled "the method" similarly includes many incorrect statements. To give a few examples, they seem to think the widely-used tree-based algorithms include only monopole and dipole, thus demonstrating a gross ignorance concerning the way how people actually use these methods. With exception of the code which runs on GRAPE hardware (well, here also you can use higher order moments now. See my paper in JCP, 1999, 151, 910-920), every existing implementation of treecode used in astrophysics implemented at least quadrupole term. Another example of the mistake is that they somehow imagined that the capability of using non-1/r potential is limited to FMM and not of treecode.
Finally, what they called "fast versions of the Ewald method" are in reality just the high-order version of particle-particle particle-mesh method, which you can find in the standard textbook (such as Hockney and Eastwood).
To summarize, this is the first time for me to find such a low-quality article with full of incorrect statements to appear in CiSE. I hope that this is an exception.
With best regards,
Jun Makino
University of Tokyo