高速多重極法

同義語:fast multipole methodFMM

概要

高速多重極法(fast multipole method)とは、平面の $N$ 個の点電荷のつくる対数ポテンシャルの和のような、すべての点の組の相互作用の和を、決めた精度で、点がほぼ一様に分布していれば点の数に比例する手間で計算する方法である。遠くの点の集まりの寄与を、1 つの中心のまわりの $p$ 項の多重極展開にまとめ、4 分木の箱の間で係数を移し替え、隣接する箱の寄与だけを直接計算する。誤差の上界は $p$ を 1 増やすごとに一定の比で小さくなる。粒子の計算や、境界要素法の密な行列とベクトルの積に使う。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: 冪級数, Laurent展開, 複素対数関数, 基本解

高速多重極法(fast multipole method、FMM)は、$N$ 個の点の間の相互作用の和
$$ \varphi(z_j)=\sum_{i\ne j}q_i\log\lvert z_j-z_i\rvert\qquad(j=1,\dots,N) $$
を、決めた精度で $O(N)$ 回の演算で計算する方法である。そのまま計算すると $N(N-1)$ 組の和で $O(N^2)$ の手間がかかる。$\log\lvert z\rvert$ は平面の $-\Delta$ の 基本解 $-\frac1{2\pi}\log\lvert z\rvert$ の $-2\pi$ 倍なので、これは点電荷のつくる 2 次元の静電ポテンシャルや重力ポテンシャルの計算であり、境界要素法 の密な行列とベクトルの積もこの形になる。
考え方は 2 つある。第 1 に、遠くにある点の集まりの寄与は、1 つの中心のまわりの少数の係数(多重極展開)にまとめられる。電荷が半径 $r$ の円板にあり、評価点が中心から $R$ 以上離れていれば、係数を $p$ 個で打ち切った誤差は $(r/R)^{p}$ 程度である(主定理)。第 2 に、平面を 4 分木で階層的に分け、遠い組を粗い箱どうしでまとめて扱い、近い組だけを直接計算する。
この記事では、点を複素数 $z\in\mathbb C$ で表す Greengard–Rokhlin の 2 次元の方法を述べ、多重極展開の打ち切り誤差、係数の平行移動の公式、アルゴリズム全体の誤差の上界、一様な分布での演算の回数を証明する。

定義と使える条件

以下、$q_i$ は実数、$z_i$ は単位正方形 $[0,1]^2\subset\mathbb C$ の点とする。点の集まり $B$ について $Q_B:=\sum_{i\in B}q_i$、$A_B:=\sum_{i\in B}\lvert q_i\rvert$ とおく。

多重極展開と局所展開

点 $c\in\mathbb C$ と $p\ge1$ について、

  1. 点の集まり $B$ の $c$ のまわりの 多重極係数 を $a_k:=-\dfrac1k\sum_{i\in B}q_i(z_i-c)^k$($k\ge1$)、$a_0:=Q_B$ とし、
    $$ M_p(z):=Q_B\log\lvert z-c\rvert+\operatorname{Re}\sum_{k=1}^p\frac{a_k}{(z-c)^k} $$
    を $p$ 項の 多重極展開 という。
  2. $c$ のまわりの次数 $p$ 以下の多項式 $\operatorname{Re}\sum_{l=0}^p\lambda_l(z-c)^l$ を 局所展開 という。

多重極展開は遠くで、局所展開は近くで使う。前者は $c$ を中心とする Laurent展開、後者は Taylor 展開(冪級数)の実部である。

4 分木・隣接・相互作用の表

$\ell=0,1,\dots,L$ について、単位正方形を $2^\ell\times2^\ell$ 個の辺 $h_\ell:=2^{-\ell}$ の正方形(水準 $\ell$ の箱)に分ける。水準 $\ell$ の箱は水準 $\ell+1$ の 4 つの箱(子)に分かれる。

  1. 同じ水準の 2 つの箱は、閉包が交わるとき 隣接 するという(箱は自分自身と隣接する)。各箱の隣接する箱は高々 $9$ 個である。
  2. 水準 $\ell\ge2$ の箱 $b$ の 相互作用の表 $\mathrm{IL}(b)$ を、$b$ の親に隣接する箱の子のうち、$b$ に隣接しないものの全体とする。高々 $36-9=27$ 個である。

同じ水準の箱が隣接しなければ、中心の間の距離は $2h_\ell$ 以上であり、箱の点は中心から $h_\ell/\sqrt2$ 以内にある。この比が誤差の上界の $\beta$ を決める。
使える条件(型 H):

  • (i) 核:$\log\lvert z-w\rvert$ のように、遠くで少数の項に展開できる核であること。この記事の公式は 2 次元の Laplace 方程式の核に限る。
  • (ii) よく離れていること:展開は、評価点と電荷の中心の距離が電荷の広がりより十分大きいときだけ使う(隣接する箱を除くのはこのため)。
  • (iii) 点の分布:$O(N)$ の演算の回数は、各葉の点の数が上限 $s$ 以下で、葉の数が $N/s$ 程度のとき成り立つ(prop-fmm-count)。強く偏った分布では、点の多いところだけを細かく分ける適応的な木を使う。

公式の表

$z_0:=c_0-c_1$ とする。$\binom nk$ は二項係数である。

操作公式条件根拠
P2M(点 → 多重極)$a_0=Q$、$a_k=-\frac1k\sum q_i(z_i-c)^k$点は $\lvert z_i-c\rvert\le r$def-fmm-expansions
打ち切り誤差$\lvert\varphi-M_p\rvert\le\dfrac{A\alpha^{p+1}}{(p+1)(1-\alpha)}$、$\alpha=r/R$$\lvert z-c\rvert\ge R>r$thm-fmm-truncation
M2M(中心 $c_0$ → $c_1$)$b_l=-\dfrac{Qz_0^l}l+\sum_{k=1}^la_kz_0^{l-k}\dbinom{l-1}{k-1}$厳密($l\le p$ は $a_1,\dots,a_l$ だけで決まる)lem-fmm-m2m
M2L(多重極 → 局所)$\lambda_0=Q\log(-z_0)+\sum_{k=1}^p\dfrac{(-1)^ka_k}{z_0^k}$、$\lambda_l=-\dfrac Q{lz_0^l}+\dfrac1{z_0^l}\sum_{k=1}^p\dfrac{(-1)^ka_k}{z_0^k}\dbinom{l+k-1}{k-1}$$d=\lvert z_0\rvert>2r$、誤差は $\dfrac{2A\beta^{p+1}}{(p+1)(1-\beta)}$、$\beta=\dfrac r{d-r}$prop-fmm-m2l
L2L(局所 → 局所)$\mu_l=\sum_{k=l}^p\lambda_k\dbinom kl(c_2-c_1)^{k-l}$多項式の平行移動で厳密二項定理
全体の誤差$\dfrac{2A\beta^{p+1}}{(p+1)(1-\beta)}$、$\beta=\dfrac1{2\sqrt2-1}\approx0.5469$一様な 4 分木thm-fmm-error

$\log(-z_0)$ の分枝はどれをとってもよい。分枝を変えても $\lambda_0$ が純虚数だけ変わり、実部をとった値は変わらないからである。

主定理と証明

多重極展開の打ち切り誤差

多重極展開の打ち切り誤差

点の集まり $B$ がすべて $\lvert z_i-c\rvert\le r$ にあるとし、$a_k$ を def-fmm-expansions の係数とする。$\lvert z-c\rvert>r$ なら
$$ \sum_{i\in B}q_i\log\lvert z-z_i\rvert=Q_B\log\lvert z-c\rvert+\operatorname{Re}\sum_{k=1}^\infty\frac{a_k}{(z-c)^k} $$
で、級数は絶対収束する。さらに $\lvert z-c\rvert\ge R>r$ なら、$\alpha:=r/R$ について
$$ \Bigl\lvert\sum_{i\in B}q_i\log\lvert z-z_i\rvert-M_p(z)\Bigr\rvert\le\frac{A_B}{p+1}\cdot\frac{\alpha^{p+1}}{1-\alpha} $$
が成り立つ。

1 つの点ごとに $\log\lvert1-w\rvert$ を展開する

$\lvert w\rvert< 1$ では、複素対数関数 の主値について $\operatorname{Log}(1-w)=-\sum_{k\ge1}w^k/k$(絶対収束)で、実部は $\log\lvert1-w\rvert$ である。$w_i:=\dfrac{z_i-c}{z-c}$ とおくと $\lvert w_i\rvert\le r/\lvert z-c\rvert< 1$ で、$z-z_i=(z-c)(1-w_i)$ なので
$$ \log\lvert z-z_i\rvert=\log\lvert z-c\rvert+\log\lvert1-w_i\rvert=\log\lvert z-c\rvert-\operatorname{Re}\sum_{k\ge1}\frac{(z_i-c)^k}{k\,(z-c)^k} $$
である。$q_i$ を掛けて $i\in B$ について足すと、有限和と絶対収束する級数の和の順序を入れ替えて最初の式を得る。
打ち切りの誤差は $\operatorname{Re}\sum_{k>p}a_k(z-c)^{-k}$ で、$\lvert a_k\rvert\le\frac1k\sum\lvert q_i\rvert r^k=A_Br^k/k$ だから
$$ \Bigl\lvert\sum_{k>p}\frac{a_k}{(z-c)^k}\Bigr\rvert\le\sum_{k>p}\frac{A_B}k\Bigl(\frac rR\Bigr)^k\le\frac{A_B}{p+1}\sum_{k\ge p+1}\alpha^k=\frac{A_B}{p+1}\cdot\frac{\alpha^{p+1}}{1-\alpha} $$
である。$\square$

誤差は $A_B$ と比 $\alpha$ だけで決まり、$B$ の中の点の個数によらない。$10^{-6}$ 程度の相対精度なら、$\alpha=\frac12$ で $p\approx17$ 項で足りる。点が何個あっても、遠くから見れば $p+1$ 個の数にまとまる。

係数の移し替え

M2M:多重極展開の中心の移動

thm-fmm-truncation の点の集まり $B$ の $c_0$ のまわりの係数を $a_k$、$c_1$ のまわりの係数を $b_l$ とする。$z_0=c_0-c_1$ について、公式の表の M2M の式が成り立つ。特に $b_1,\dots,b_p$ は $Q_B,a_1,\dots,a_p$ から正確に計算できる。

要点:$z_i-c_1=(z_i-c_0)+z_0$ を二項定理で展開する。

詳しい証明を開く

$w_i:=z_i-c_0$ とおくと、二項定理 から $(z_i-c_1)^l=\sum_{k=0}^l\binom lkw_i^kz_0^{l-k}$ である。よって $$b_l=-\frac1l\sum_iq_i(z_i-c_1)^l=-\frac{Q_Bz_0^l}l+\sum_{k=1}^l\frac1l\binom lk\Bigl(\sum_iq_iw_i^k\Bigr)z_0^{l-k}\cdot(-1).$$ $-\sum_iq_iw_i^k=ka_k$ と $\frac kl\binom lk=\binom{l-1}{k-1}$ を使うと表の式になる。右辺は $k\le l$ の $a_k$ しか含まない。$\square$

M2M は近似を含まない。親の箱の $p$ 項の係数は、子の箱の $p$ 項の係数から正確に計算できる。

M2L:局所展開とその誤差

点の集まり $B$ が $\lvert z_i-c_0\rvert\le r$ にあり、$d:=\lvert c_0-c_1\rvert>2r$ とする。$Q_B,a_1,\dots,a_p$ から公式の表の M2L の式で $\lambda_0,\dots,\lambda_p$ を作ると、$\lvert z-c_1\rvert\le r$ のすべての $z$ で
$$ \Bigl\lvert\sum_{i\in B}q_i\log\lvert z-z_i\rvert-\operatorname{Re}\sum_{l=0}^p\lambda_l(z-c_1)^l\Bigr\rvert\le\frac{2A_B}{p+1}\cdot\frac{\beta^{p+1}}{1-\beta},\qquad\beta:=\frac r{d-r}< 1 $$
が成り立つ。

誤差を 2 つに分ける

$z_0=c_0-c_1$、$u:=(z-c_1)/z_0$ とおく。$\lvert z-c_1\rvert\le r$ なら $\lvert u\rvert\le r/d< \frac12$ である。
表の式の意味. $z-c_0=-z_0(1-u)$ なので、$\log\lvert z-c_0\rvert=\log\lvert z_0\rvert+\log\lvert1-u\rvert=\operatorname{Re}\bigl(\log(-z_0)-\sum_{l\ge1}u^l/l\bigr)$ であり、負の 2 項級数 $(1-u)^{-k}=\sum_{l\ge0}\binom{k+l-1}lu^l$ から
$$ (z-c_0)^{-k}=\frac{(-1)^k}{z_0^k}\sum_{l\ge0}\binom{k+l-1}{l}\frac{(z-c_1)^l}{z_0^l} $$
である。$\binom{k+l-1}l=\binom{l+k-1}{k-1}$ なので、M2L の $\lambda_l$ は $p$ 項の多重極展開 $M_p$ を $c_1$ のまわりに展開した係数のうち次数 $p$ 以下のものである。
誤差の分解. 多重極展開を $p$ 項で切ると、thm-fmm-truncation の式から $\sum_iq_i\log\lvert z-z_i\rvert=M_p(z)+\operatorname{Re}E(z)$、$E(z):=\sum_{k>p}a_k(z-c_0)^{-k}$ である。$M_p$ の展開を次数 $p$ で切った多項式を $T_pM_p$、$E$ の展開を次数 $p$ で切ったものを $T_pE$ と書くと、求めたい差は
$$ \bigl(\textstyle\sum_iq_i\log\lvert z-z_i\rvert-\operatorname{Re}T_p[M_p+E]\bigr)+\operatorname{Re}T_pE $$
である。
第 1 項. 点ごとに $z-z_i=(c_1-z_i)(1+v_i)$、$v_i:=\frac{z-c_1}{c_1-z_i}$ と書く。$\lvert c_1-z_i\rvert\ge d-r$ なので $\lvert v_i\rvert\le\beta< 1$ で、$\log\lvert z-z_i\rvert=\log\lvert c_1-z_i\rvert+\operatorname{Re}\sum_{l\ge1}(-1)^{l+1}v_i^l/l$ である。これは $z-c_1$ の冪級数の実部である。$M_p+E$ も円板 $\lvert z-c_1\rvert< d-r$ で $z-c_1$ の冪級数で表され、実部が等しい 2 つの冪級数は定数項の虚部を除いて一致するので、$\sum_iq_i\log\lvert z-z_i\rvert$ の次数 $p$ までの部分は $\operatorname{Re}T_p[M_p+E]$ に等しい。残りは $\sum_{l>p}\beta^l/l$ を $\lvert q_i\rvert$ 倍して足したもの以下で、$\frac{A_B}{p+1}\frac{\beta^{p+1}}{1-\beta}$ 以下である。
第 2 項. 上の式から $(z-c_0)^{-k}$ の $l$ 次の係数の絶対値は $\binom{k+l-1}ld^{-k-l}$ なので、$\lvert a_k\rvert\le A_Br^k/k$ と合わせて
$$ \lvert T_pE(z)\rvert\le\sum_{k>p}\lvert a_k\rvert d^{-k}\sum_{l\ge0}\binom{k+l-1}l\Bigl(\frac rd\Bigr)^l=\sum_{k>p}\frac{\lvert a_k\rvert}{(d-r)^k}\le\sum_{k>p}\frac{A_B}k\beta^k\le\frac{A_B}{p+1}\cdot\frac{\beta^{p+1}}{1-\beta} $$
である($\sum_l\binom{k+l-1}lx^l=(1-x)^{-k}$)。2 つを足して主張を得る。$\square$

L2L は次数 $p$ の多項式を別の中心のまわりに書き直すだけなので、近似を含まない。

アルゴリズム全体の誤差

遠い点はちょうど 1 回数えられる

深さ $L\ge2$ の 4 分木で、点 $z$ を含む水準 $\ell$ の箱を $b_\ell(z)$ と書く。2 点 $z,w$ について、$b_L(z)$ と $b_L(w)$ が隣接しないなら、$b_\ell(w)\in\mathrm{IL}(b_\ell(z))$ となる水準 $\ell\in\{2,\dots,L\}$ はちょうど 1 つである。隣接するなら、そのような $\ell$ はない。

要点:$b_\ell(z)$ と $b_\ell(w)$ が隣接しなくなる最初の水準だけが数える。

詳しい証明を開く

子は親に含まれるので、ある水準で隣接しない 2 つの箱の子孫どうしも隣接しない。したがって「$b_\ell(z)$ と $b_\ell(w)$ が隣接する」は $\ell$ について下に閉じている。水準 $1$ の 4 つの箱は互いに隣接する。$b_L(z)$ と $b_L(w)$ が隣接しないとき、隣接しない最小の水準を $\ell_0$($2\le\ell_0\le L$)とする。$b_{\ell_0-1}(z)$ と $b_{\ell_0-1}(w)$ は隣接するので、$b_{\ell_0}(w)$ は $b_{\ell_0}(z)$ の親に隣接する箱の子で、$b_{\ell_0}(z)$ に隣接しないから $\mathrm{IL}(b_{\ell_0}(z))$ に入る。$\ell< \ell_0$ では $b_\ell(z)$ と $b_\ell(w)$ が隣接するので入らない。$\ell>\ell_0$ では親どうし $b_{\ell-1}(z)$、$b_{\ell-1}(w)$ が隣接しないので入らない。$b_L(z)$ と $b_L(w)$ が隣接するときは、すべての水準で隣接するので入らない。$\square$

高速多重極法の誤差

深さ $L\ge2$ の一様な 4 分木で、下の「計算の手順」を $p$ 項の展開で行って得た値を $\tilde\varphi(z_j)$ とする。すべての $j$ で
$$ \lvert\tilde\varphi(z_j)-\varphi(z_j)\rvert\le\frac{2A}{p+1}\cdot\frac{\beta^{p+1}}{1-\beta},\qquad A:=\sum_i\lvert q_i\rvert,\quad\beta:=\frac1{2\sqrt2-1}\approx0.546918 $$
が成り立つ。

誤差は箱ごとの M2L の誤差の和

$z=z_j$ を固定し、$b_\ell:=b_\ell(z)$ とする。lem-fmm-m2m により、各箱の $p$ 項の係数は、その箱の点の $p$ 項の多重極係数に正確に等しい。L2L は正確なので、葉 $b_L$ の局所展開は、各水準 $\ell$ と各 $B\in\mathrm{IL}(b_\ell)$ について $B$ の係数から M2L で作った多項式の和である。
lem-fmm-partition により、点 $z_i$($i\ne j$)は、$b_L$ に隣接する葉にあれば直接の和で正確に 1 回数えられ、そうでなければちょうど 1 つの水準 $\ell$ で、ちょうど 1 つの $B\in\mathrm{IL}(b_\ell)$ を通して数えられる。よって誤差は、それらの $B$ についての M2L の誤差の和である。
水準 $\ell$ の箱の辺を $h$ とすると、$B$ の点は中心 $c_0$ から $r=h/\sqrt2$ 以内、$z$ は $b_\ell$ の中心 $c_1$ から $r$ 以内にあり、$B$ と $b_\ell$ は隣接しないので $d=\lvert c_0-c_1\rvert\ge2h>2r$ である。prop-fmm-m2l の $\beta=\frac r{d-r}$ は $\frac{h/\sqrt2}{2h-h/\sqrt2}=\frac1{2\sqrt2-1}$ 以下で、誤差は $\frac{2A_B}{p+1}\frac{\beta^{p+1}}{1-\beta}$ 以下である。各点は高々 1 つの $B$ に入るので $\sum_BA_B\le A$ で、主張を得る。$\square$

上界は $p$ を 1 増やすごとに約 $0.547$ 倍になる。相対誤差 $\lvert\tilde\varphi-\varphi\rvert/A$ を $\varepsilon$ 以下にするには、$p\approx\log(1/\varepsilon)/\log(2\sqrt2-1)\approx1.66\log(1/\varepsilon)$ 項で足りる。

一様な分布での演算の回数

深さ $L$ の 4 分木で、すべての葉の点の数が $s$ 以下であり、$4^L\le4N/s$ とする。複素数の四則演算と対数の計算の回数は、点の数によらない定数 $C$ について
$$ C\Bigl(Np+\frac Nsp^2+Ns\Bigr) $$
以下である。$p$ と $s$ を固定すれば $O(N)$、$s$ を $p$ に比例させれば $O(Np)$ である。

要点:箱の数は $\frac43\cdot4^L\le\frac{16N}{3s}$ で、各箱で行う平行移動は高々 $27+2$ 回、1 回は $O(p^2)$ である。

詳しい証明を開く

水準 $2$ から $L$ までの箱の数は $\sum_{\ell=2}^L4^\ell< \frac43\cdot4^L\le\frac{16N}{3s}$ である。P2M は 1 点あたり $p$ 個の冪の更新で $O(Np)$。M2M・L2L は各箱で 1 回ずつ、M2L は各箱で高々 $27$ 回(def-fmm-tree)で、1 回の平行移動は表の式で $O(p^2)$ なので、合わせて $O\bigl(\frac Nsp^2\bigr)$。葉での局所展開の評価は 1 点あたり $O(p)$ で $O(Np)$。直接の和は、各点について隣接する高々 $9$ 個の葉の点、すなわち $9s$ 個以下の相手なので $O(Ns)$ である。$\square$

計算の手順

  1. 木を作る:点を含む正方形を 4 分木に分け、葉の点の数がおよそ $s$ になる深さ $L$ を選ぶ(一様な分布なら $L\approx\log_4(N/s)$)。展開の項数 $p$ を thm-fmm-error の上界から決める。
  2. 上向き(P2M・M2M):各葉で点から $p$ 項の多重極係数を計算し、水準 $L-1$ から $2$ まで、子の係数を lem-fmm-m2m で親の中心へ移して足す。
  3. 下向き(M2L・L2L):水準 $2$ から $L$ まで、各箱 $b$ について、親の局所展開を L2L で $b$ の中心へ移し、$\mathrm{IL}(b)$ の各箱の多重極係数を prop-fmm-m2l で局所展開に変えて足す。
  4. 評価:各葉の点で、局所展開の多項式の実部を Horner 法で計算し、隣接する葉(自分を含む)の点からの寄与を直接足す(自分自身の項 $i=j$ は除く)。
    手順が終わる回数は prop-fmm-count のとおりで、誤差は thm-fmm-error で保証される。手順 4 の直接の和は誤差を含まない。

例題

多重極展開の打ち切り

問題:単位円板の中の $10$ 個の点($\max\lvert z_i\rvert\approx0.971943$)に $[-1,1]$ の一様乱数の電荷($A\approx4.113708$)を置き、中心 $0$ の $p$ 項の多重極展開で円 $\lvert z\rvert=R$ の上の値を計算したときの最大誤差を、thm-fmm-truncation の上界($r=1$)と比べよ。
答え:

$R$$p$最大誤差上界
25$1.193\times10^{-3}$$2.143\times10^{-2}$
210$1.763\times10^{-5}$$3.652\times10^{-4}$
220$7.011\times10^{-9}$$1.868\times10^{-7}$
410$5.925\times10^{-9}$$1.189\times10^{-7}$
420$3.109\times10^{-15}$$5.939\times10^{-14}$

$R$ を 2 倍にすると $\alpha$ が $\frac12$ から $\frac14$ になり、上界は同じ $p$ でおよそ $2^{-(p+1)}$ 倍になる。実際の誤差も同じ程度に減っている。誤差は円周の $721$ 点での最大値で、乱数は種 $529$ の擬似乱数である。

一様な点での誤差

問題:単位正方形に一様に $N=2000$ 点をとり(種 $529$)、電荷を $[-1,1]$ の一様乱数として、深さ $L=4$(葉 $256$ 個、1 個あたり平均約 $7.8$ 点)の木で $\tilde\varphi$ を計算し、直接の和との最大誤差を調べよ。
答え:$A\approx1005.76$、$\max\lvert\varphi\rvert\approx52.90$ で、

$p$最大誤差thm-fmm-error の上界
4$3.100\times10^{-2}$$43.45$
8$3.984\times10^{-4}$$2.160$
12$1.119\times10^{-5}$$0.1338$
16$2.382\times10^{-7}$$9.153\times10^{-3}$
20$4.938\times10^{-9}$$6.630\times10^{-4}$

上界は電荷の符号の打ち消し合いを無視しているので大きいが、$p$ による減り方の速さは上界と同じか、より速い。M2L は $6900$ 回、直接の和の組($i\ne j$)は $127886$ 組で、直接の和だけで計算すると $N(N-1)=3998000$ 組である。
図: 例題の点で、展開の項数 p を増やしたときの最大誤差と誤差の上界を片対数で描いた図 図: 例題の点で、展開の項数 p を増やしたときの最大誤差と誤差の上界を片対数で描いた図

演算の回数の増え方

問題:葉の平均の点の数を $16$ に保って $N$ を $4$ 倍ずつ増やし($N=1024,4096,16384,65536$、$L=3,4,5,6$)、直接の和の組と M2L の回数を数えよ。
答え:直接の和の組は $N$ あたり $121.3,\ 132.1,\ 137.6,\ 141.1$、M2L は $N$ あたり $1.24,\ 1.69,\ 1.95,\ 2.09$ で、どちらも $N$ あたりほぼ一定である(目安はそれぞれ $9\cdot16-1=143$ と、$27\cdot\frac43\cdot\frac1{16}=2.25$)。直接の和だけなら $N=65536$ で約 $4.29\times10^9$ 組になる。

使える条件と反例

外す条件例何が起こるか破れる結論
評価点が電荷の円板の外(thm-fmm-truncation の $\lvert z-c\rvert>r$)$q=1$ を $z_1=0.9$、$c=0$、$r=1$ に置き、$z=0.5$ で評価項 $\frac{a_k}{z^k}=-\frac1k(1.8)^k$ が $0$ に近づかない級数が発散し、展開そのものが成り立たない
よく離れていること(隣接する箱を M2L に含める)辺 $h$ の隣り合う箱、$d=h$、$r=h/\sqrt2$$\beta=\frac r{d-r}=\frac1{\sqrt2-1}\approx2.414>1$prop-fmm-m2l の上界が無意味になる。$B$ の点が共有する辺の中点にあると、$b$ の中心までの距離 $h/2$ が $r$ より小さく、局所展開は $b$ 全体では収束しない
葉の点の数の上限(prop-fmm-count)$N$ 個の点がすべて 1 つの葉に入る直接の和だけで $N(N-1)$ 組$O(N)$ の演算の回数
反例の確かめ

1 行目:$a_k=-\frac1k(0.9)^k$ なので $\frac{a_k}{0.5^k}=-\frac{1.8^k}k$ で、$k\to\infty$ で絶対値は $\infty$ に発散する。2 行目:$z_i$ を共有する辺の中点にとると $\lvert c_1-z_i\rvert=h/2$ で、$\log\lvert z-z_i\rvert$ を $c_1$ のまわりに展開した冪級数の収束半径は $h/2$ である。$b$ には $c_1$ から $h/\sqrt2>h/2$ 離れた角の点があるので、局所展開は $b$ 全体では収束しない。3 行目:深さ $L$ を固定して点を 1 か所に集めれば、その葉の点の数は $N$ で、prop-fmm-count の仮定の $s$ が $N$ になる。

よくある誤り

誤り正しくはなぜ
誤差は点の数 $N$ とともに増える上界は $A=\sum\lvert q_i\rvert$ と $\beta^{p}$ で決まり、$N$ によらない形で書けるthm-fmm-error
M2M や L2L のたびに誤差がたまるどちらも厳密で、誤差は M2L だけで生じるlem-fmm-m2m、L2L の行
隣接する箱も展開で扱ってよい隣接する箱は直接の和で計算する反例の表の 2 行目
どんな分布でも $O(N)$一様な木では、点の偏りで葉が大きくなる。適応的な木を使う反例の表の 3 行目
複素対数の分枝の選び方で結果が変わる実部をとるので分枝によらない公式の表の後の注意

補足

3 次元. 3 次元の核 $1/\lvert x-y\rvert$ では、多重極展開に 球面調和関数 を使う。1 点の電荷については Legendre多項式 の例「点電荷のポテンシャルの展開」がその最初の形である。平面の 4 分木のかわりに空間の 8 分木を使う。
ほかの核と応用. Helmholtz方程式やStokes方程式の核にも同じ考えの方法がある。境界要素法 では、密な行列とベクトルの積を高速多重極法で計算し、反復法と組み合わせて大きな問題を解く。局所展開を使わず、各点ごとに木をたどって遠くの箱の寄与をまとめて近似する方法(Barnes–Hut の方法)もある。

関連項目

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する