{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "0",
   "metadata": {},
   "source": [
    "# 11.1.5 FMM for point clouds\n",
    "\n",
    "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\n",
    "\n",
    "$$\n",
    "u(x_j) = \\sum_{i=1}^N K(x_j, y_i) \\, q_i \\qquad \\forall j, 1 \\leq j \\leq M,\n",
    "$$\n",
    "\n",
    "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$:\n",
    "\n",
    "$$\n",
    "G(x,y) = \\frac{1}{4 \\pi |x-y|} \\qquad \\text{or} \\qquad G(x,y) = \\frac{e^{i \\kappa |x-y|}}{4 \\pi |x-y|}\n",
    "$$\n",
    "\n",
    "Every kernel formula below is checked against a direct summation with numpy, which prints the maximal error relative to the maximal value.\n",
    "\n",
    "The idea behind the method is explained in [11.1.1](intro_fmm.ipynb) and [11.1.2](basisfunctions.ipynb)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "1",
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "from ngsolve.fmm import FMM\n",
    "\n",
    "rng = np.random.default_rng(1)\n",
    "N, M = 2000, 500\n",
    "sources = rng.random((N, 3))                  # the y_i, one point per row\n",
    "targets = rng.random((M, 3)) + (0.5, 0, 0)    # the x_j\n",
    "\n",
    "def relerr(u, ref):\n",
    "    return np.max(np.abs(u - ref)) / np.max(np.abs(ref))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2",
   "metadata": {},
   "source": [
    "## Charges and potentials\n",
    "\n",
    "The defaults are `kernel=\"laplace\"`, `source=\"charges\"` and `target=\"potential\"`:\n",
    "\n",
    "$$\n",
    "u(x_j) = \\sum_{i=1}^N \\frac{q_i}{4 \\pi |x_j - y_i|}\n",
    "$$\n",
    "\n",
    "The operator is set up once, and `op @ q` returns the potential as a new numpy array:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "3",
   "metadata": {},
   "outputs": [],
   "source": [
    "op = FMM(sources, targets)\n",
    "q = rng.standard_normal(N)\n",
    "u = op @ q\n",
    "print(u.shape, u.dtype)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4",
   "metadata": {},
   "source": [
    "The direct sum for comparison, with the $M \\times N$ matrix of all interactions:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "5",
   "metadata": {},
   "outputs": [],
   "source": [
    "d = targets[:, None, :] - sources[None, :, :]    # x_j - y_i, shape (M,N,3)\n",
    "r = np.linalg.norm(d, axis=2)\n",
    "G = 1 / (4 * np.pi * r)\n",
    "print(f\"error: {relerr(u, G @ q):.1e}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6",
   "metadata": {},
   "source": [
    "The operator can be applied to further densities without being set up again, `op(q)` is the same as `op @ q`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "7",
   "metadata": {},
   "outputs": [],
   "source": [
    "for k in range(3):\n",
    "    qk = rng.standard_normal(N)\n",
    "    print(f\"error: {relerr(op(qk), G @ qk):.1e}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8",
   "metadata": {},
   "source": [
    "## Helmholtz kernel\n",
    "\n",
    "`kernel=\"helmholtz\"` needs a nonzero wave number `kappa`, real or complex:\n",
    "\n",
    "$$\n",
    "u(x_j) = \\sum_{i=1}^N \\frac{e^{i \\kappa |x_j - y_i|}}{4 \\pi |x_j - y_i|} \\, q_i\n",
    "$$\n",
    "\n",
    "The potential is complex, the density may be real or complex."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "9",
   "metadata": {},
   "outputs": [],
   "source": [
    "for kappa in [10, 10+2j]:\n",
    "    op = FMM(sources, targets, kernel=\"helmholtz\", kappa=kappa)\n",
    "    q = rng.standard_normal(N) + 1j * rng.standard_normal(N)\n",
    "    Gk = np.exp(1j * kappa * r) / (4 * np.pi * r)\n",
    "    print(f\"kappa = {kappa}: error {relerr(op @ q, Gk @ q):.1e}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "10",
   "metadata": {},
   "source": [
    "## Dipoles and gradients\n",
    "\n",
    "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:\n",
    "\n",
    "$$\n",
    "K(x, y_i) = n_i \\cdot \\nabla_y G(x, y_i) = \\frac{\\langle x - y_i, n_i \\rangle}{4 \\pi r^3} \\, (1 - i \\kappa r) \\, e^{i \\kappa r}, \\qquad r = |x - y_i|,\n",
    "$$\n",
    "\n",
    "with $\\kappa = 0$ for the Laplace kernel."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "11",
   "metadata": {},
   "outputs": [],
   "source": [
    "normals = rng.standard_normal((N, 3))\n",
    "q = rng.standard_normal(N)\n",
    "dn = np.einsum(\"jik,ik->ji\", d, normals)       # <x_j - y_i, n_i>\n",
    "\n",
    "op = FMM(sources, targets, source=\"dipoles\", source_normals=normals)\n",
    "print(f\"Laplace:   error {relerr(op @ q, (dn / (4 * np.pi * r**3)) @ q):.1e}\")\n",
    "\n",
    "kappa = 10\n",
    "op = FMM(sources, targets, kernel=\"helmholtz\", kappa=kappa, source=\"dipoles\", source_normals=normals)\n",
    "Kdip = dn * (1 - 1j * kappa * r) * np.exp(1j * kappa * r) / (4 * np.pi * r**3)\n",
    "print(f\"Helmholtz: error {relerr(op @ q, Kdip @ q):.1e}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "12",
   "metadata": {},
   "source": [
    "`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\n",
    "\n",
    "$$\n",
    "\\nabla_x G(x, y) = \\frac{(i \\kappa r - 1) \\, e^{i \\kappa r}}{4 \\pi r^3} \\, (x - y).\n",
    "$$\n",
    "\n",
    "The gradient is also available for dipoles."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "13",
   "metadata": {},
   "outputs": [],
   "source": [
    "op = FMM(sources, targets, kernel=\"helmholtz\", kappa=kappa, target=\"gradient\")\n",
    "gradu = op @ q\n",
    "gradG = ((1j * kappa * r - 1) * np.exp(1j * kappa * r) / (4 * np.pi * r**3))[:, :, None] * d\n",
    "print(gradu.shape, f\"error {relerr(gradu, np.einsum('jik,i->jk', gradG, q)):.1e}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "14",
   "metadata": {},
   "source": [
    "## Sources as targets\n",
    "\n",
    "Without `targets` the sources are the targets as well. The singular pairs $x_j = y_i$ contribute zero:\n",
    "\n",
    "$$\n",
    "u(y_j) = \\sum_{i \\neq j} G(y_j, y_i) \\, q_i\n",
    "$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "15",
   "metadata": {},
   "outputs": [],
   "source": [
    "op = FMM(sources)\n",
    "rs = np.linalg.norm(sources[:, None, :] - sources[None, :, :], axis=2)\n",
    "np.fill_diagonal(rs, np.inf)                    # i = j contributes 1/inf = 0\n",
    "Gs = 1 / (4 * np.pi * rs)\n",
    "print(f\"error: {relerr(op @ q, Gs @ q):.1e}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "16",
   "metadata": {},
   "source": [
    "## Vector-valued densities\n",
    "\n",
    "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)$.\n",
    "\n",
    "An example from electromagnetics: point currents $J_i$ at the $y_i$ have the vector potential $A$ and the magnetic field $B$\n",
    "\n",
    "$$\n",
    "A(x) = \\sum_i G(x, y_i) \\, J_i, \\qquad\n",
    "B(x) = \\operatorname{curl} A(x) = \\sum_i \\nabla_x G(x, y_i) \\times J_i = \\sum_i \\frac{(i \\kappa r - 1) \\, e^{i \\kappa r}}{4 \\pi r^3} \\, (x - y_i) \\times J_i.\n",
    "$$\n",
    "\n",
    "`source=\"curl\"` computes $B$ directly; it needs `kernel=\"helmholtz\"`, `components=3` and `target=\"potential\"`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "17",
   "metadata": {},
   "outputs": [],
   "source": [
    "kappa = 2\n",
    "J = rng.standard_normal((N, 3))\n",
    "A = FMM(sources, targets, kernel=\"helmholtz\", kappa=kappa, components=3) @ J\n",
    "B = FMM(sources, targets, kernel=\"helmholtz\", kappa=kappa, components=3, source=\"curl\") @ J\n",
    "print(A.shape, B.shape)\n",
    "\n",
    "Gk = np.exp(1j * kappa * r) / (4 * np.pi * r)\n",
    "gradG = ((1j * kappa * r - 1) * Gk / r**2)[:, :, None] * d\n",
    "print(f\"A: error {relerr(A, Gk @ J):.1e}\")\n",
    "print(f\"B: error {relerr(B, np.cross(gradG, J[None, :, :]).sum(axis=1)):.1e}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "18",
   "metadata": {},
   "source": [
    "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$:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "19",
   "metadata": {},
   "outputs": [],
   "source": [
    "opgrad = FMM(sources, targets, kernel=\"helmholtz\", kappa=kappa, components=3, target=\"gradient\")\n",
    "g = opgrad @ J\n",
    "curlA = np.stack([g[:, 2, 1] - g[:, 1, 2], g[:, 0, 2] - g[:, 2, 0], g[:, 1, 0] - g[:, 0, 1]], axis=1)\n",
    "print(g.shape, f\"curl A - B: {relerr(curlA, B):.1e}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "20",
   "metadata": {},
   "source": [
    "## As an NGSolve operator\n",
    "\n",
    "`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):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "21",
   "metadata": {},
   "outputs": [],
   "source": [
    "print(opgrad.shape)\n",
    "x = opgrad.mat.CreateRowVector()\n",
    "y = opgrad.mat.CreateColVector()\n",
    "x.FV().NumPy()[:] = J.ravel()\n",
    "y.data = opgrad.mat * x\n",
    "print(f\"error: {relerr(y.FV().NumPy(), g.ravel()):.1e}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "22",
   "metadata": {},
   "source": [
    "So the FMM can be used inside NGSolve's iterative solvers. As an example we take the second kind integral equation\n",
    "\n",
    "$$\n",
    "\\rho(x) + \\int_{\\Omega} G(x,y) \\, \\rho(y) \\, dy = f(x), \\qquad x \\in \\Omega = (0,1)^3,\n",
    "$$\n",
    "\n",
    "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:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "23",
   "metadata": {},
   "outputs": [],
   "source": [
    "from ngsolve.la import IdentityMatrix\n",
    "from ngsolve import solvers\n",
    "\n",
    "K = FMM(sources).mat\n",
    "lhs = IdentityMatrix(N) + (1/N) * K\n",
    "f = K.CreateColVector()\n",
    "f.FV().NumPy()[:] = np.sin(np.pi * sources[:, 0])\n",
    "\n",
    "inv = solvers.GMRESSolver(lhs, IdentityMatrix(N), tol=1e-12, printrates=False)\n",
    "rho = f.CreateVector()\n",
    "rho.data = inv * f\n",
    "print(\"iterations:\", inv.iterations)\n",
    "\n",
    "rho_dense = np.linalg.solve(np.eye(N) + Gs / N, f.FV().NumPy())\n",
    "print(f\"error: {relerr(rho.FV().NumPy(), rho_dense):.1e}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "24",
   "metadata": {},
   "source": [
    "## Accuracy and cost\n",
    "\n",
    "Keyword arguments control the FMM, see `help(FMM)`:\n",
    "\n",
    "* `fmm_minorder` (default 20) and `fmm_order_factor` (default 2.0): a box with half side $r$ uses the expansion order `fmm_minorder` + `fmm_order_factor` $\\cdot |\\kappa| r$.\n",
    "* `fmm_maxdirect` (default 100): a box with this many sources (targets) or more is subdivided.\n",
    "* `fmm_separation` (default 2.0): admissibility factor of the box-box translations.\n",
    "* `fmm_maxlevel` (default 20): the maximal level of the subdivision.\n",
    "* `fmm_split_kr` (default 20.0): a box with $|\\kappa| r$ $\\geq$ `fmm_split_kr` is subdivided further.\n",
    "\n",
    "Lower orders are faster and less accurate, and a box holding all points sums directly:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "25",
   "metadata": {},
   "outputs": [],
   "source": [
    "import time\n",
    "\n",
    "q = rng.standard_normal(N)\n",
    "ref = G @ q\n",
    "for minorder in [2, 5, 10, 20, 30]:\n",
    "    start = time.perf_counter()\n",
    "    u = FMM(sources, targets, fmm_minorder=minorder) @ q\n",
    "    print(f\"fmm_minorder = {minorder:2}: error {relerr(u, ref):.1e}, time {1000 * (time.perf_counter() - start):.1f} ms\")\n",
    "\n",
    "u = FMM(sources, targets, fmm_maxdirect=10000) @ q\n",
    "print(f\"fmm_maxdirect = 10000:  error {relerr(u, ref):.1e}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "26",
   "metadata": {},
   "source": [
    "## Running on the GPU\n",
    "\n",
    "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.\n",
    "\n",
    "`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.\n",
    "\n",
    "```python\n",
    "import ngsolve.gpu\n",
    "\n",
    "op = FMM(sources, targets, device=\"gpu\", fp32=True)\n",
    "u = op @ q\n",
    "```\n",
    "\n",
    "On the CPU, `fp32=True` gives errors of single precision size:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "27",
   "metadata": {},
   "outputs": [],
   "source": [
    "u32 = FMM(sources, targets, fp32=True, device=\"none\") @ q\n",
    "print(f\"fp32=True: error {relerr(u32, ref):.1e}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "28",
   "metadata": {},
   "source": [
    "## Evaluation at points not known in advance\n",
    "\n",
    "`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](layerpotentials.ipynb)."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.13.11"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
