The fast multipole method has been called one of the ten most significant algorithms in scientific computation discovered in the 20th century (along with algorithms such as the FFT).

The algorithm allows the product of particular dense matrices with a vector to be evaluated approximately (to a specified precision ) in O(Nlog N) operations, when direct multiplication requires O(N²) operations. These matrices are those whose elements arise from distributions of points {x} and {y} in R^d, i.e. each element of the matrix can be represented as

A_ij=j(x_i,y_j).

Coupled with advances in iterative methods for the solution of linear systems, they provide O(N log N) time and memory complexity solutions of problems that hitherto required O(N³) or O(N²) time complexity and O(N²) memory complexity. For extremely large problems, the gain in efficiency and memory can be very significant.

It turns out that many practical problems lead to large dense matrices that are amenable to the use of  fast multipole methods. These include solution of

• Laplace and Poisson equations
• Helmholtz equation
• Maxwell's equation
• Stokes flow
• computational statistics (Gaussian, logistic, probit, etc. sums)
• machine learning (kernel sums)
• molecular dynamics simulations (long range component of forces)
• N-body problems in stellar dynamics
• interpolation of scattered data (biharmonic, multiquadric, polyharmonic, Gaussian sums)
• implicit surface fitting
• nonuniform fast Fourier algorithms
• Yukawa potentials

In fact if you have a dense matrix calculation or a large summation, it is likely the FMM may be applicable to your algorithm after some analysis.

Why is the FMM not very widely used?

A natural question to ask is if the FMM is indeed as efficient as is claimed here, then why is it not as much used? There are probably several historical reasons for this. First, as the FMM is an analysis based algorithm it needs some analytical work to develop the FMM and then some care in translating that analysis in to software. Second, to achieve fast software, the FMM data structures must be properly implemented. Third, once the software is implemented, care should be taken that it is adaptive, so that the efficiency of the algorithm is maintained. This adaptivity includes the use of different translation methods, the number of levels in the data structure, available memory and others.

Because of these reasons the FMM is not as widely known or is perceived of as a difficult to implement algorithm.

Fantalgo's software

Our FMM software is tested and demonstrated to show efficiency on many test problems, and is ready to be included in your application. Further, we are able to take advantage of multicore processing that is commonly available on modern workstations to further speed-up the code.