Stochastic Systems Group
Home Research Group Members Programs  
Demos Calendar Publications Mission Statement Alumni

SSG Seminar Abstract

An Overview of Fast Multipole Methods

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 so-called N-body 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 low-rank block matrix approximations, first discussing a heuristic block-matrix 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