Stochastic Systems Group  

Alex Ihler  SSG, MIT
We present some background and results from the body of work collectively referred to as "fast multipole methods" (FMM). These comprise a set of techniques for speeding up socalled Nbody problems, in which a potential function composed of a sum of pairwise interaction terms from N points is evaluated at an equally large number of locations. We present these methods from the viewpoint of lowrank block matrix approximations, first discussing a heuristic blockmatrix approximation method (Kapur, 1997), then moving into the analytic expansions which form the basis of both the original and new versions of the fast multipole method (Greengard, 1997). We attempt to provide sufficient background to understand and compute all the relevant results, yet present the material in sufficient generality that it is easy to understand the relationship to similar algorithms such as the fast Gauss transform (Greengard, 1998).
Problems with this site should be emailed to jonesb@mit.edu