This page was generated from unit-11.1-fmm/fmm_pointclouds.ipynb.
11.1.5 FMM for point clouds¶
The module ngsolve.fmm provides the fast multipole method for plain point clouds given as numpy arrays, no mesh or finite element space is needed. FMM computes the sums
for sources \(y_i\) with densities \(q_i\) and targets \(x_j\), in \(O(N+M)\) instead of \(O(NM)\) operations. The kernels are built from Green’s function of the Laplace equation, or of the Helmholtz equation with wave number \(\kappa\):
Every kernel formula below is checked against a direct summation with numpy, which prints the maximal error relative to the maximal value.
The idea behind the method is explained in 11.1.1 and 11.1.2.
[1]:
import numpy as np
from ngsolve.fmm import FMM
rng = np.random.default_rng(1)
N, M = 2000, 500
sources = rng.random((N, 3)) # the y_i, one point per row
targets = rng.random((M, 3)) + (0.5, 0, 0) # the x_j
def relerr(u, ref):
return np.max(np.abs(u - ref)) / np.max(np.abs(ref))
Charges and potentials¶
The defaults are kernel="laplace", source="charges" and target="potential":
The operator is set up once, and op @ q returns the potential as a new numpy array:
[2]:
op = FMM(sources, targets)
q = rng.standard_normal(N)
u = op @ q
print(u.shape, u.dtype)
(500,) float64
The direct sum for comparison, with the \(M \times N\) matrix of all interactions:
[3]:
d = targets[:, None, :] - sources[None, :, :] # x_j - y_i, shape (M,N,3)
r = np.linalg.norm(d, axis=2)
G = 1 / (4 * np.pi * r)
print(f"error: {relerr(u, G @ q):.1e}")
error: 6.5e-09
The operator can be applied to further densities without being set up again, op(q) is the same as op @ q:
[4]:
for k in range(3):
qk = rng.standard_normal(N)
print(f"error: {relerr(op(qk), G @ qk):.1e}")
error: 2.7e-09
error: 8.6e-09
error: 4.1e-09
Helmholtz kernel¶
kernel="helmholtz" needs a nonzero wave number kappa, real or complex:
The potential is complex, the density may be real or complex.
[5]:
for kappa in [10, 10+2j]:
op = FMM(sources, targets, kernel="helmholtz", kappa=kappa)
q = rng.standard_normal(N) + 1j * rng.standard_normal(N)
Gk = np.exp(1j * kappa * r) / (4 * np.pi * r)
print(f"kappa = {kappa}: error {relerr(op @ q, Gk @ q):.1e}")
kappa = 10: error 7.2e-10
kappa = (10+2j): error 8.9e-10
Dipoles and gradients¶
With source="dipoles" every source has a direction \(n_i\), given as source_normals (an \((N,3)\) array, used as given, not normalised). The kernel is the derivative of \(G\) with respect to the source point, the kernel of the double layer potential:
with \(\kappa = 0\) for the Laplace kernel.
[6]:
normals = rng.standard_normal((N, 3))
q = rng.standard_normal(N)
dn = np.einsum("jik,ik->ji", d, normals) # <x_j - y_i, n_i>
op = FMM(sources, targets, source="dipoles", source_normals=normals)
print(f"Laplace: error {relerr(op @ q, (dn / (4 * np.pi * r**3)) @ q):.1e}")
kappa = 10
op = FMM(sources, targets, kernel="helmholtz", kappa=kappa, source="dipoles", source_normals=normals)
Kdip = dn * (1 - 1j * kappa * r) * np.exp(1j * kappa * r) / (4 * np.pi * r**3)
print(f"Helmholtz: error {relerr(op @ q, Kdip @ q):.1e}")
Laplace: error 6.2e-09
Helmholtz: error 1.2e-09
target="gradient" evaluates the gradient of \(u\) with respect to the target point, an \((M,3)\) array with u[j,k] \(= \partial u / \partial x_k (x_j)\). For charges the kernel is
The gradient is also available for dipoles.
[7]:
op = FMM(sources, targets, kernel="helmholtz", kappa=kappa, target="gradient")
gradu = op @ q
gradG = ((1j * kappa * r - 1) * np.exp(1j * kappa * r) / (4 * np.pi * r**3))[:, :, None] * d
print(gradu.shape, f"error {relerr(gradu, np.einsum('jik,i->jk', gradG, q)):.1e}")
(500, 3) error 1.1e-09
Sources as targets¶
Without targets the sources are the targets as well. The singular pairs \(x_j = y_i\) contribute zero:
[8]:
op = FMM(sources)
rs = np.linalg.norm(sources[:, None, :] - sources[None, :, :], axis=2)
np.fill_diagonal(rs, np.inf) # i = j contributes 1/inf = 0
Gs = 1 / (4 * np.pi * rs)
print(f"error: {relerr(op @ q, Gs @ q):.1e}")
error: 2.9e-09
Vector-valued densities¶
With components=3 the kernel acts on three densities at once, with one FMM tree: the density is an \((N,3)\) array, the potential an \((M,3)\) array, and the gradient an \((M,3,3)\) array with u[j,c,k] \(= \partial u_c / \partial x_k (x_j)\).
An example from electromagnetics: point currents \(J_i\) at the \(y_i\) have the vector potential \(A\) and the magnetic field \(B\)
source="curl" computes \(B\) directly; it needs kernel="helmholtz", components=3 and target="potential".
[9]:
kappa = 2
J = rng.standard_normal((N, 3))
A = FMM(sources, targets, kernel="helmholtz", kappa=kappa, components=3) @ J
B = FMM(sources, targets, kernel="helmholtz", kappa=kappa, components=3, source="curl") @ J
print(A.shape, B.shape)
Gk = np.exp(1j * kappa * r) / (4 * np.pi * r)
gradG = ((1j * kappa * r - 1) * Gk / r**2)[:, :, None] * d
print(f"A: error {relerr(A, Gk @ J):.1e}")
print(f"B: error {relerr(B, np.cross(gradG, J[None, :, :]).sum(axis=1)):.1e}")
(500, 3) (500, 3)
A: error 5.9e-09
B: error 1.8e-08
The curl of \(A\) from its gradient, \((\operatorname{curl} A)_1 = \partial_2 A_3 - \partial_3 A_2\) and so on, agrees with \(B\):
[10]:
opgrad = FMM(sources, targets, kernel="helmholtz", kappa=kappa, components=3, target="gradient")
g = opgrad @ J
curlA = np.stack([g[:, 2, 1] - g[:, 1, 2], g[:, 0, 2] - g[:, 2, 0], g[:, 1, 0] - g[:, 0, 1]], axis=1)
print(g.shape, f"curl A - B: {relerr(curlA, B):.1e}")
(500, 3, 3) curl A - B: 1.8e-08
As an NGSolve operator¶
op.mat is the operator as an NGSolve BaseMatrix. It acts on the flat vectors, the ravel() of the numpy arrays, and op.shape is its (height, width):
[11]:
print(opgrad.shape)
x = opgrad.mat.CreateRowVector()
y = opgrad.mat.CreateColVector()
x.FV().NumPy()[:] = J.ravel()
y.data = opgrad.mat * x
print(f"error: {relerr(y.FV().NumPy(), g.ravel()):.1e}")
(4500, 6000)
error: 0.0e+00
So the FMM can be used inside NGSolve’s iterative solvers. As an example we take the second kind integral equation
and discretise it with the sources as quadrature points with equal weights \(1/N\), leaving out the singular diagonal (a crude Nyström method). With the sources-as-targets operator \(K\) from above this is the linear system \((I + \frac{1}{N} K) \rho = f\), which we solve with GMRes:
[12]:
from ngsolve.la import IdentityMatrix
from ngsolve import solvers
K = FMM(sources).mat
lhs = IdentityMatrix(N) + (1/N) * K
f = K.CreateColVector()
f.FV().NumPy()[:] = np.sin(np.pi * sources[:, 0])
inv = solvers.GMRESSolver(lhs, IdentityMatrix(N), tol=1e-12, printrates=False)
rho = f.CreateVector()
rho.data = inv * f
print("iterations:", inv.iterations)
rho_dense = np.linalg.solve(np.eye(N) + Gs / N, f.FV().NumPy())
print(f"error: {relerr(rho.FV().NumPy(), rho_dense):.1e}")
iterations: 7
error: 2.3e-11
Accuracy and cost¶
Keyword arguments control the FMM, see help(FMM):
fmm_minorder(default 20) andfmm_order_factor(default 2.0): a box with half side \(r\) uses the expansion orderfmm_minorder+fmm_order_factor\(\cdot |\kappa| r\).fmm_maxdirect(default 100): a box with this many sources (targets) or more is subdivided.fmm_separation(default 2.0): admissibility factor of the box-box translations.fmm_maxlevel(default 20): the maximal level of the subdivision.fmm_split_kr(default 20.0): a box with \(|\kappa| r\) \(\geq\)fmm_split_kris subdivided further.
Lower orders are faster and less accurate, and a box holding all points sums directly:
[13]:
import time
q = rng.standard_normal(N)
ref = G @ q
for minorder in [2, 5, 10, 20, 30]:
start = time.perf_counter()
u = FMM(sources, targets, fmm_minorder=minorder) @ q
print(f"fmm_minorder = {minorder:2}: error {relerr(u, ref):.1e}, time {1000 * (time.perf_counter() - start):.1f} ms")
u = FMM(sources, targets, fmm_maxdirect=10000) @ q
print(f"fmm_maxdirect = 10000: error {relerr(u, ref):.1e}")
fmm_minorder = 2: error 7.5e-03, time 49.0 ms
fmm_minorder = 5: error 3.2e-04, time 58.0 ms
fmm_minorder = 10: error 5.2e-06, time 38.2 ms
fmm_minorder = 20: error 5.6e-09, time 55.5 ms
fmm_minorder = 30: error 1.4e-11, time 123.4 ms
fmm_maxdirect = 10000: error 2.9e-15
Running on the GPU¶
After import ngsolve.gpu, device="gpu" runs the FMM on the GPU (an error if there is none), and the default device="auto" uses the GPU if it can, else the CPU. Without that import, "auto" stays on the CPU. device="cpu" runs the same device kernels on the host.
fp32=True computes the FMM in single precision: the expansions, their translations and the direct sums between nearby points. Densities and results stay double precision numpy arrays. GPUs without float64, such as Apple GPUs with Metal, need fp32=True: without it device="gpu" raises an error there, and "auto" stays on the CPU.
import ngsolve.gpu
op = FMM(sources, targets, device="gpu", fp32=True)
u = op @ q
On the CPU, fp32=True gives errors of single precision size:
[14]:
u32 = FMM(sources, targets, fp32=True, device="none") @ q
print(f"fp32=True: error {relerr(u32, ref):.1e}")
fp32=True: error 1.6e-07
Evaluation at points not known in advance¶
FMM fixes the targets when the operator is set up. To evaluate the potential of given sources at arbitrary points later on, fill a SingularMLExpansion from ngsolve.fmm with AddCharges or AddDipoles, call Calc, and use Evaluate(points), see their docstrings. Such expansions are also used in 11.1.3 Layer potentials.