Fast multipole method

Builds on Multipole expansion Fundamental solution of the Laplacian

Definition

Let $x_1, \dots, x_N$ be points in $\R^d$ with $d = 2$ or $3$ , and let $q_1, \dots, q_N$ be real numbers. Let $G$ be a kernel such as the fundamental solution of the Laplacian. The task is to compute the potentials $\phi_i = \sum_{j \ne i} q_j G(x_i, x_j)$ for $i = 1, \dots, N$ . The fast multipole method with expansion order $p$ computes approximations of all $\phi_i$ as follows.

Enclose the points in a box. Subdivide it recursively into $2^d$ children, giving a tree, until each leaf box holds a bounded number of points.
For each leaf, form the multipole expansion of its points truncated at order $p$ . Going up the tree, translate the expansions of the children to the centre of the parent and add them.
For each box, convert the multipole expansions of the well-separated boxes in its interaction list into one local expansion about its centre. Add to it the local expansion inherited from its parent.
At each leaf, evaluate the local expansion at its points, and add the interactions with points in the neighbouring leaves directly.

Remarks

Example: in the plane, identify $\R^2$ with $\C$ and take $G(z, w) = \log \abs{z - w}$ . For points $z_j$ in a disc of centre $c$ and radius $r$ , and for $\abs{z - c} > r$ , $\sum_j q_j \log(z - z_j) = Q \log(z - c) - \sum_{k \ge 1} \frac{1}{k} \sum_j q_j \frac{(z_j - c)^k}{(z - c)^k}, \qquad Q = \sum_j q_j.$ This follows from $\log(z - z_j) = \log(z - c) + \log\big(1 - \frac{z_j - c}{z - c}\big)$ and the series of $\log(1 - u)$ . The potential is the real part, and keeping $p$ terms gives an error of order $(r / \abs{z - c})^p$ .

Non-example: the Barnes–Hut tree code also groups far points by boxes, but it has no step 3: each point is evaluated against far boxes one by one. Its cost is $O(N \log N)$ , not $O(N)$ .

For a fixed order $p$ and points that are not too unevenly spread, the cost of the method is $O(N)$ , and the error decreases geometrically as $p$ grows.

Reading path

To understand this page from the ground up, read these 19 pages in order. The foundations come first.

Show the path as a graph

Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.

no evidence level

Euclidean space object
Function concept
Fundamental solution concept
Multipole expansion concept
Total derivative concept
Function of several variables concept
Vector-valued function concept
Laplace transform definition
Differentiable function of several variables concept
Partial derivative concept
Vector field concept
Heaviside step function object
Gradient concept
Divergence concept
Dirac delta function object
Laplacian concept
Harmonic function concept
Fundamental solution of the Laplacian definition
Fast multipole method definition

Tag	`B4Z227Q9PN`
URI	`m2://B4Z227Q9PN`
Kind	definition
Writing	W0 stub
MSC	65Y20, 78M16, 70F10
Defines	Fast multipole method
Uses	Multipole expansion, Fundamental solution of the Laplacian
Changed	3 November 2026

Fast multipole method

Definition

Remarks

Reading path

Further reading

What this page needs for W1

What links here