Fast multipole method

The fast multipole method (FMM) is a numerical technique that was developed to speed up the calculation of long-ranged forces in the n-body problem. It does this by expanding the system Green's function using a multipole expansion, which allows one to group sources that lie close together and treat them as if they are a single source.

The FMM has also been applied in accelerating the iterative solver in the method of moments (MOM) as applied to computational electromagnetics problems. The FMM was first introduced in this manner by Greengard and Rokhlin and is based on the multipole expansion of the vector Helmholtz equation. By treating the interactions between far-away basis functions using the FMM, the corresponding matrix elements do not need to be explicitly stored, resulting in a significant reduction in required memory. If the FMM is then applied in a hierarchical manner, it can improve the complexity of matrix-vector products in an iterative solver from ${\displaystyle {\mathcal {O}}(N^{2})}$ to ${\displaystyle {\mathcal {O}}(N)}$ in finite arithmetic, i.e., given a tolerance ${\displaystyle \epsilon }$, the matrix-vector product is guaranteed to be within a tolerance ${\displaystyle \epsilon }$. The dependence of the complexity on the tolerance ${\displaystyle \epsilon }$ is ${\displaystyle {\mathcal {O}}(\log(1/\epsilon ))}$, i.e., the complexity of FMM is ${\displaystyle {\mathcal {O}}(\log(1/\epsilon )N)}$. This has expanded the area of applicability of the MOM to far greater problems than were previously possible.

...
Wikipedia