HN 日本語サマリー

← 一覧へ戻る
科学・技術

分解されたサブドメイン上でのウォーク

Walk on Decomposed Subdomains (clementjambon.github.io)

31 pointsby E-Reverance2 コメント

要約

この記事は、楕円形偏微分方程式(PDE)を解くためのグリッドフリーモンテカルロ法、特にWalk on Spheres (WoS)とWalk on Stars (WoSt)について論じています。複雑な形状に対する従来の有限差分法や有限要素法の課題を指摘し、ドメインを小さなサブドメインに分割し、決定論的ソルバーと組み合わせることで、モンテカルロ法の効率と精度を向上させる新しいアプローチを提案しています。

全文翻訳

分解されたサブドメイン上のウォーク:楕円形PDEのためのハイブリッドモンテカルロ・決定論ソルバー

Blog post by Clément Jambon.

1 楕円形PDEと境界値問題

多くの現実世界の現象は、楕円形偏微分方程式(PDE)によって支配されています。例えば、熱伝導、静電場、経路計画、定常ポテンシャル流などです。これらはしばしば境界値問題(BVP)として定式化され、領域の境界で値が指定され、内部のPDEの解を求めます。

ディリクレ境界条件を持つラプラス方程式を例に考えてみましょう。

$$ \begin{cases} \Delta u = 0 & \text{in } \Omega \ u = g & \text{on } \partial\Omega_D \end{cases} $$

以下のインタラクティブな図で、これが何をするのか直感的に掴んでみてください。

Brush value +1.00

−1 (cold)+1 (hot)

Presets

外側の境界帯をクリックしてペイントすることでディリクレ値 $g$ を設定します。内部は $\Delta u=0$ を満たします。

ディリクレ問題。 正方形領域におけるディリクレ境界条件を持つラプラス方程式の解。

より複雑な形状や境界条件を考慮することで、問題をより面白くすることができます。例えば、ノイマン境界条件を持つ混合境界値問題の解法に関心が持たれることがよくあります(ここではゼロ・ノイマン条件に限定します)。

$$ \begin{cases} \Delta u = 0 & \text{in } \Omega \ u = g & \text{on } \partial\Omega_D \ \frac{\partial u}{\partial n} = 0 & \text{on } \partial\Omega_N \end{cases} $$

以下のインタラクティブな図がこれを例示しています。アイソライン(等高線)がゼロ・ノイマン障害物に垂直に曲がって接し、$\frac{\partial u}{\partial n} = 0$ を満たす様子に注目してください。

Brush value +1.00

−1 (cold)+1 (hot)

Scene

Boundary presets

以前と同様に、ディリクレ帯をクリックしてペイントしてください。内部の障害物(破線、灰色)は $\partial u/\partial n = 0$ を強制します — アイソラインはそれに垂直に曲がって接します。

混合問題。 外側の境界にディリクレ値がペイントされ、内部にゼロ・ノイマン形状を持つラプラス方程式の解。

よく見ると、解は実際には「ピクセル化」されていることがわかります。これは、グリッド上での有限差分法で計算されているためです。有限差分法は理解しやすく実装も容易ですが、複雑な形状の扱いは得意ではなく、しばしば極端なグリッド細分化が必要になります。もう一つの一般的な代替手段は有限要素法を使用することです。しかし、有限要素法は慎重なメッシュ生成を必要とし、都市のような複雑な形状の場合、特に困難で時間のかかる作業となる可能性があります(車を設計していて、デザインを少し変更するたびにメッシュを再生成しなければならないと想像してみてください。それは悪夢でしょう — そして実際そうなのです!)。

[画像: 都市の周りの風。このシーンには、複雑な形状を持つ何百もの建物が含まれています。私たちの手法は、ここで定常ポテンシャル流線として可視化される、風パターンへのそれらの影響を特徴づけています。]

2 グリッドフリーモンテカルロ法

幸いなことに、コンピュータグラフィックスコミュニティは最近、古いアイデアであるグリッドフリーモンテカルロ法を復活させました。このアプローチの根幹をなす代表的なアルゴリズムは、Walk on Spheres(WoS)アルゴリズムです。

確率微分法からの直感は、内部点 $x$ から開始したブラウン運動(連続的なランダムウォーク)をシミュレートした場合、最終的に境界のあるランダムな場所 $Z_\tau$ で境界に到達するということです。そのランダムな場所での境界条件の値の期待値 $\mathbb{E}[g(Z_\tau)]$ は、ディリクレ問題の解と正確に一致します。

ブラウン運動とラプラス方程式。 粒子は内部点 $x$ から開始し、境界のあるランダムな場所 $Z_\tau$ で吸収されるまで拡散します。境界は $g$ で色付けされており、$g(Z_\tau)$ を多くのウォークで平均すると $u(x)$ が復元されます。

内部の各点でこれを独立に行うことで、全体の解が得られます。各点につき数回のウォークでは推定値はノイズが多いですが、平均する回数を増やすにつれて分散は徐々に消滅し、滑らかな調和解が現れます。これは下の図に示されています。

Refresh rate: 1 walks/frame

slowfast

low $u$ high $u$

内部の各ピクセルは、$u(x)=\mathbb{E}[g(Z_\tau)]$ の独立したWalk-on-Spheres推定を実行します。ピクセルあたりのウォーク数を増やすと、フィールドのノイズが減り調和解に近づきます。これは連続的に実行され、スライダーで速度を設定できます。

Number of samples: 1

段階的なモンテカルロ推定。 同じ正方形のディリクレ問題が、今度は各ピクセルでモンテカルロ法によって解かれています。各ピクセルは多くのランダムウォークを平均します。サンプル数が少ないと内部はノイズが多く、サンプル数が増えるにつれてノイズは徐々に消えていきます。

しかし、ブラウン運動のシミュレーションは計算コストが高く、しばしばバイアスがかかります(通常、固定時間ステップでオイラー・丸山法などを用いて離散化する必要があります)。Walk on Spheresアルゴリズムは、球面上でのブラウン運動の出口分布が正確に一様であるという観察によって、これを克服します。これにより、代わりに各球面の境界から次の球面へとホップすることができ、各球は領域に内接しており、収束を速くするために可能な限り大きく選択されます(ウォークは正確に境界に到達できないため、境界の周りに薄い $\epsilon$ 層を導入し、そこに到達したウォークを吸収させます)。

プロセス全体は、以下のインタラクティブな図に示されています。ノイマン境界条件の場合、WoSの特殊なバリアントであるWalk on Stars(WoSt)が存在することがわかります(名前が示すように、この方法はノイマン(反射)境界条件をより良く扱うために「スター上を歩く」方法です。以下のインタラクティブな図からは、それはそれほど明白ではありません。理由は、長方形の場合、角のため、星形領域は球のスライスのように見えるからです)。モンテカルロ法によるPDE解法についてさらに詳しく知りたい場合は、こちらに素晴らしいコースとリソースがあります。

[図]

モンテカルロ法は本当に魔法のようです!しかし、上記のインタラクティブな図を操作してわかるように、ランダムウォークは境界に到達するまでに多くのステップを要します。これは、複雑な形状やノイマン境界優位の問題では特に顕著です(私たちの論文では、図1の倉庫、図4の都市、図15の迷路など、これらの例の多くを示しています)。主な結果は分散と収束の遅さであり、信頼できる解が必要なシナリオでは実用的でなくなります(そして、これが人々がこれらの方法を実用化することに躊躇してきた理由かもしれません)。

私たちの研究では、この問題に2つの補完的な方法で取り組みます(これらの問題に取り組んだのは私たちが最初であると付け加えるべきです。それを解決する方法は数多くありました。私たちの独自性と主な貢献は、モンテカルロ推定の効率を改善したり、解をキャッシュしたりするだけでなく、グリッドフリーモンテカルロ法をグリッドベースのソルバーに接続する方法を提案し、後者の優れた特性を活用することです)。第一に、図に示すように、領域をより小さなサブドメインに分割することでウォークを短くすることができます。第二に、後で導入するように、決定論的ソルバーと結合することで(制御可能な)離散化バイアスの代償を払って分散を「殺す」ことができ、決定論的グリッドベース手法の優れた「分散フリー」特性を回復させます。

3 分割統治:短いウォーク

問題が複雑な場合、自然な解決策はそれを小さく、より管理しやすい部分に分割することです。これは数値手法における一般的な戦略です:領域分割、マルチグリッド、階層行列など。そして、まさに私たちが論文で採用した経路です。

まず、$\Delta u = 0$ が領域 $\Omega$ のどこでも成り立つという美しい性質に注目してください。したがって、領域をより小さなサブドメインに分割することで、ウォークを短くできるという直感が働きます。

より正式には、領域を小さな非重複サブドメインの集合 $\mathcal{D}={\Omega_i}$ の分割として提案します。例えば、規則的なタイルです。各タイルでは、ディリクレ境界は(a)$\partial\Omega_D$ から継承した物理的なディリクレ部分と、(b)人工的なディリクレ部分 — 隣接タイルとのインターフェイス — の和集合です。この分割にはメッシュ生成は必要ないことに注意してください。サブドメインは完全に任意であり、ノイマン境界と交差してもよく、領域 $\Omega$ の外部をカバーすることもできます。

タイル内のウォークは、以下のインタラクティブな図に示すように、タイルの境界で停止するようになります。タイリング解像度を調整して、ヒストグラムでのウォーク長にどのように影響するか確認してください。

[図]

この戦略は、Walks in Decomposed Subdomains(分解されたサブドメイン内のウォーク)をもたらします。では、なぜ論文のタイトルがWalks on Decomposed Subdomains(分解されたサブドメイン上のウォーク)なのでしょうか?まだ道半ばです。これらのウォークだけでは、まだ多くのことはわかりません。サブドメイン間のインターフェイスの値がまだわからないのです。

ここでグリッドベースソルバーとの関連性が登場します。しかし、それ以前に、ポアソンカーネルと解演算子を理解する必要があります。

4 ポアソンカーネルと解演算子

単一のタイル $\Omega_i$ 内では、$\Delta u = 0$ も成り立つため、境界値を知れば内部解が一意に決定されます。具体的には、これを境界値を内部値にマッピングする線形演算子 $\mathcal{H}_i$ としてエンコードできます。

$$\mathcal{H}_i : \partial\Omega_i \to \Omega_i $$

つまり、$u(x) = \mathcal{H}_i[u](x)$ はすべての $x \in \Omega_i$ に対して成り立ちます。しかし、$\mathcal{H}_i$ をどのように得るのでしょうか?それは局所的にはPDEの解なのですから…

そのアイデアは、$\mathcal{H}_i$ が積分形式で書けるという観察にあります。

$$ u(x) = \int extbackslash partial\Omega_i P extbackslash Omega_i(x, z), u(z), dz $$

ここで、$P extbackslash Omega_i(x, z)$ はポアソンカーネルと呼ばれます。重要な観察は、$P extbackslash Omega_i(x, z)$ が、点 $x$ から開始して境界上の点 $z$ に到達するブラウン運動の最初の到達確率密度と正確に一致するということです。待ってください — それはまさにWalk on Spheresが計算するものと違うでしょうか?

その通りです。そして、それを近似するための簡単なレシピが得られます。点 $x \in \Omega_i$ に対して、多くのランダムウォークを $x$ から開始し、$\partial\Omega_i$ 上のどこで終了するかをビン分けします。以下のインタラクティブな図は、この戦略を用いて表計算された様々な領域のポアソンカーネルを可視化しています。

[図]

ポアソンカーネルには二重の解釈があります。点 $x$ を固定してウォークがどこで終了するかを尋ねる代わりに、境界上の点 $z$ を固定して、どの内部点がそこへウォークを送る可能性が最も高いかを尋ねます。言い換えれば、ディリクレ境界上の点 $z$ における単位点ソースが内部にどのように影響するか — これがまさに解演算子です!

[図]

[図]

[図]

上記のインタラクティブな図が示唆するように、解演算子を単純な行列 $\mathbf{H}$ として事前に計算し離散化する自然で簡単な方法があります(これが最も効率的な方法であるとは主張しません。ここには改善の余地が巨大にあります!)。下の図に示すように、行方向では、$H extbackslash ij$ は $x extbackslash i$ から境界への最初の到達確率を表し、列方向では、$H extbackslash ij$ は単位ソース $z extbackslash j$ に対する内部応答を与えます。

[画像: 離散解演算子 H が z_j を含む境界パネルを内部点 x_i にマッピング]

離散解演算子。 内部を配置点 ${x_i} \subset \Omega$ で離散化し、ディリクレ境界 $\partial\Omega_D$ を配置点 ${z_j}$ を持つパネル ${\Gamma_j}$ に離散化すると、解演算子を近似する行列 $\mathbf{H}$ が得られます。行方向では、$H extbackslash ij$ は $x extbackslash i$ から開始したウォークがパネル $\Gamma_j$ を通過する確率であり、列方向では、$H extbackslash ij$ は $x extbackslash i$ における単位ソース $z extbackslash j$ に対する内部応答を与えます。

各タイル $\Omega_i$ に対して1つの離散解演算子 $\mathbf{H}_i$ を表計算することで、各タイル内の離散ディリクレ問題を単純な行列ベクトル乗算で解くことができます。しかし、これだけではタイル間のインターフェイスの値を見つける方法がわかりません。ここで吸収マルコフ連鎖が登場します。

5 吸収マルコフ連鎖

吸収マルコフ連鎖もランダムウォークですが、今回は離散的(かつ有限)な状態集合 $\mathcal{S}$ 上で行われます。一部の状態 $\mathcal{T}$ は遷移状態(ウォーカーはそれらを通過する可能性があり、何度も通過するかもしれません)と呼ばれ、残りの状態 $\mathcal{A}$ は吸収状態(一度入ると、ウォーカーは二度と出ない)と呼ばれ、$\mathcal{S} = \mathcal{T} \sqcup \mathcal{A}$ となります。下の図は簡単な例を示しています。

吸収マルコフ連鎖。 3つの遷移状態 $\mathcal{T}={t_1,t_2,t_3}$ が2つの吸収状態 $\mathcal{A}={a_L,a_R}$ の間にあります。各ステップでウォーカーはランダムな隣接状態に移動します。吸収状態は自己ループを持ち、一度そこに到達するとウォーカーは永遠にそこに留まります。

重要な観察は、吸収マルコフ連鎖上で、境界値問題に類似したものを定義できるということです。具体的には、以下のインタラクティブな例に示すように、吸収状態に値を指定し、遷移状態からウォークを開始して吸収されるまで実行し、吸収された値の平均を取ることで、遷移状態で定義された解を得ることができます。つまり、$$u(t) = \mathbb{E}[g(A_\tau) \mid X_0 = t]$$ は任意の遷移状態 $t \in \mathcal{T}$ に対して成り立ちます。ここで、$A_\tau \in \mathcal{A}$ はウォークが終了する吸収状態であり、$g$ は吸収状態での指定された値を保持します。これはWalk on Spheresアルゴリズムに非常に似ていませんか?

以下のインタラクティブな図は、2つの吸収終端をリンクする単純なマルコフ連鎖の例を示しています。

+1 −1

+1 −1

walks: 0

各吸収終端の隣にある垂直スライダーをドラッグして境界値を設定します。遷移ノードのいずれかをクリックしてウォークを開始します。各ノードの下にあるスライダーをドラッグして遷移確率を変更します。各内部円の内側の色は、実行中のモンテカルロ推定値です。「Run walks」で多くのウォークを開始するか、「Show exact solve」で正確な解を表示できます。

離散境界値問題。 遷移状態からウォークを開始し、吸収状態での値の合計を取ることで、離散境界値問題の解を近似できます。

任意に遷移確率を選択でき、それらが解にどのように影響するかを観察してください(ネタバレ:次のセクションでは、ポアソンカーネルによって与えられる幾何学的に情報化された値を遷移確率として選択します!)。

最後の楽しいこと!状態がいくつかしかなくても、モンテカルロ推定値が揺れ動かなくなるまで、かなりの数のウォークを開始する必要があることに気づいたかもしれません。そこで自然な疑問が生じます。本当にランダムウォークをシミュレートする必要があるのでしょうか?

任意の遷移状態 $i$ を見てください。記憶喪失性により、マルコフ連鎖では、状態 $i$ にいるウォーカーは確率 $P extbackslash ij$ で隣接状態 $j$ に1ステップ移動し、そこからの残りのウォークは状態 $j$ から開始した新しいウォークと統計的に同じです。言い換えれば、状態 $i$ で吸収される期待値は、その隣接状態での期待値の加重平均にすぎません。

$$ \begin{aligned} u(i) &;=; \sum extbackslash j \in \mathcal{S} P extbackslash ij, u(j) && \text{on } \mathcal{T}, \ u(a) &;=; g(a) && \text{on } \mathcal{A}. \end{aligned} $$

これはラプラス方程式の離散的な類推です。各内部値はその隣接値の平均であり、境界値が指定されています(連続的なケースでは、この平均値の性質はラプラシアン演算子がゼロであることによって局所的に捉えられます。しかし、積分的な意味でも成り立ちます。 $u(x) = \frac{1}{|\partial B(x, R)|}\int extbackslash partial B(x, R) u(z),dz$ は中心 $x$、半径 $R$ のボールに対して成り立ちます)。ランダムウォークは静かに姿を消しました。未知数が遷移値である線形方程式系が残りました。

これを具体的にするために、遷移行列を遷移状態間と遷移状態から吸収状態へのブロックに分割し、

$$ \mathbf{P} ;=; \begin{bmatrix} \mathbf{Q} & \mathbf{R} \ \mathbf{0} & \mathbf{I} \end{bmatrix}, $$

未知の遷移状態値をベクトル $\mathbf{u} extbackslash \mathcal{T}$ に、指定された吸収状態値を $\mathbf{g}$ に集めます。上記の平均化恒等式は $\mathbf{u} extbackslash \mathcal{T} = \mathbf{Q},\mathbf{u} extbackslash \mathcal{T} + \mathbf{R},\mathbf{g}$ となり、つまり、

$$ (\mathbf{I} - \mathbf{Q}), \mathbf{u} extbackslash \mathcal{T} ;=; \mathbf{R}, \mathbf{g}. $$

これで完了です。すべてのウォークが最終的に吸収される限り(確率は1です)、$\mathbf{I} - \mathbf{Q}$ は可逆であり、単一の線形ソルブで、すべての遷移状態での正確な期待吸収値が一度に得られます。サンプリングなし、分散なし、推定値が落ち着くのを待つ必要もありません。上記の図で「Show exact solve」を試してみてください。色はすぐに最終値にスナップするはずです!

最後に一つ面白いことを。
$\mathbf{I}-\mathbf{P}$ をランダムウォークのラプラシアンと見なすことができます。1Dでは、対称ランダムウォークを選択した場合、対応するランダムウォークのラプラシアンはあなたにとって非常に馴染み深いものになるはずです。それは(スケーリング係数を無視すれば)正確に1Dの3点差分ラプラシアンです。

i-2

i-1

i

i+1

i+2

h

h

$\tfrac{1}{2}$

$\tfrac{1}{2}$

$$ \begin{aligned} \big[(\mathbf{I}-\mathbf{P}),\mathbf{u}] extbackslash i &;=; u extbackslash i - \tfrac{1}{2}u extbackslash i-1 - \tfrac{1}{2}u extbackslash i+1 \ &;=; -\tfrac{h^2}{2},\underbrace{\frac{u extbackslash i-1 - 2u extbackslash i + u extbackslash i+1}{h^2}} extbackslash \Delta_h u extbackslash i. \end{aligned} $$

1Dランダムウォークラプラシアン。 間隔 $h$ の一様グリッド上の対称ランダムウォークでは、演算子 $\mathbf{I}-\mathbf{P}$ は、スケーリング係数 $-h^2/2$ を除いて、標準的な3点差分ラプラシアン $\Delta_h$ と正確に一致します。

そして2Dでは、一様グリッド上の対称ウォークのランダムウォークラプラシアンは、標準的な5点差分ステンシルを復元します。

i,,j+1

i-1,,j

i,,j

i+1,,j

i,,j-1

h

h

$\tfrac{1}{4}$

$\tfrac{1}{4}$

$\tfrac{1}{4}$

$\tfrac{1}{4}$

$$ \begin{aligned} \big[(\mathbf{I}-\mathbf{P}),\mathbf{u}] extbackslash i,j &;=; u extbackslash i,j - \tfrac{1}{4}\big(u extbackslash i-1,j + u extbackslash i+1,j + u extbackslash i,j-1 + u extbackslash i,j+1\big) \ &;=; -\tfrac{h^2}{4},\underbrace{\frac{u extbackslash i-1,j + u extbackslash i+1,j + u extbackslash i,j-1 + u extbackslash i,j+1 - 4u extbackslash i,j}{h^2}} extbackslash \Delta_h u extbackslash i,j. \end{aligned} $$

2Dランダムウォークラプラシアン。 間隔 $h$ の一様正方形グリッド上の対称ランダムウォークでは、演算子 $\mathbf{I}-\mathbf{P}$ は、スケーリング係数 $-h^2/4$ を除いて、標準的な5点差分ラプラシアン $\Delta_h$ と正確に一致します。

そこから、おそらくパターンが見えてくるでしょう。これらの標準的な確率の代わりに、サブドメインの幾何学的形状に基づいたより一般的な遷移確率を考慮するとどうなるでしょうか?

6 吸収マルコフ連鎖によるタイルの結合

これで、サブドメイン間のインターフェイスの値を取り戻すためのほとんどすべてのピースが揃いました!トリックは、分解されたサブドメイン上をウォークする、より正確にはそれらのインターフェイス上をウォークすることです。

最後の問題は、これまでのところ、サブドメインの内部からインターフェイスへのジャンプしか見ておらず、インターフェイスから別のインターフェイスへのジャンプは見ていないことです。その修正は、各インターフェイスを別の分割(今回は重複する分割)を通して見ることによって行われます。その分割では、インターフェイスはサブドメインの内部にあります。グリッド上では、そのサブドメインはエッジを共有する2つのセルにすぎず、その境界は隣接するインターフェイス(またはグローバル境界の一部)で構成されます。これらを「コエッジ」サブドメインと呼びます。

Tiling resolution: 6×6 Walk speed: 1×

Tile interfaces Current co-edge subdomain Neumann obstacles

ウォーカーはインターフェイスからインターフェイスへホップします。各ホップで、それはタイルインターフェイス上にあり、そのエッジを共有する2つのタイルがコエッジサブドメイン(青)を形成します。次に、そのサブドメインの境界上の均一にランダムな出口にジャンプします(障害物内の任意の点を拒否サンプリングします)。これは新しいインターフェイスに着地し、次のコエッジサブドメインを再中心化します。最終的にグローバル境界 $Z_\tau$ に到達するまで続きます。(単純で教育的な図:出口上の均一分布であり、真の調和測度ではありません。)インターフェイスをクリックすると、そこからウォークが開始されます。リリースでランダムスタートを再開します。

Current co-edge subdomain

コエッジサブドメイン上のウォーク。 インターフェイス上の点 $x$ から、そのコエッジサブドメイン — そのインターフェイスを共有する2つのタイルの和集合 — 上をウォークすることでステップを取ります。各出口は新しいインターフェイスに着地し、次のステップのために新しいサブドメインが設定され、ウォークがグローバルディリクレ境界 $Z_\tau$ で吸収されるまで続きます。

これにより、インターフェイスを遷移状態、グローバルディリクレ境界を吸収状態とし、インターフェイス間の最初の到達確率を遷移確率として定義する(そして、コエッジサブドメインに適用された戦略を使用して推定する)離散マルコフ連鎖を定義できます。マルコフ連鎖の形式主義により、インターフェイス値を直接、決定論的(スパース)線形ソルブを通して解くことができます。これにより、そうでなければ必要とされる比較的長く、分散が大きいランダムウォークを回避できます。

インターフェイスの値がわかると、すべてのタイルの境界が一意に決定され、内部の解演算子(つまり、セクション4で定義された$\mathbf{H}_i$)を適用することで、並列に各タイルの内部を復元します。これらのタイルごとの再構築は独立しており、したがって自明に並列化可能です。

以下のインタラクティブな図は、パイプラインのすべてのステップを要約しています。様々な段階をスライドして、さまざまなパラメータを操作してみてください。

Pipeline stage: 0 — Domain

01234

Tiles per axis T: 4 Subtile resolution B: 4

N = T × B = 16

Neumann obstacle

Boundary presets

Dirichlet boundary Neumann obstacle Tile interfaces

パイプラインをスライドします。

分解されたサブドメイン上のウォーク(WoDS)パイプライン。 (1) $\Omega$ をインターフェイスで区切られたタイル ${\Omega_i}$ に分割します。(2) 各タイルについて、短いローカルWalk-on-Starsウォークでインターフェイス間の最初の到達遷移確率を推定します。これらをタイルごとの演算子 $\mathbf{H}_i$ に組み立てます。(3) 対応する確率をインターフェイス上のグローバル吸収マルコフ連鎖にステッチし、単一のスパースソルブ $(\mathbf{I}-\mathbf{Q}),\mathbf{u} extbackslash \mathcal{T} = \mathbf{R},\mathbf{g}$ を介してインターフェイス値を復元します。(4) 各タイルの境界がわかったら、ローカル内部解演算子、つまり $\mathbf{H}_i$ を適用して、内部を並列に再構築します。

7 追加の利点

これまで触れてこなかったことですが、実際には、ドメインのすべてのタイルの解演算子を計算する必要はありません。タイルがジオメトリと交差しない場合、その解演算子はどこでも同じであり、すべてのシーンで一度だけ事前に計算できます(実際には閉形式の表現があります)。つまり、推定する必要のある解演算子の数は、ドメインサイズではなく、幾何学的複雑さに応じて増加します(2Dでは面積)。これにはもう一つの大きな利点があります。シーンの一部のみが変更される場合(多くの設計またはシミュレーションワークフローで一般的です)、影響を受けるタイルのみを再推定すればよいのです。

Tiles per axis $T$: 10×10 Scene

MC-estimated tiles: —

Precomputed (shared): —

Intersects geometry — needs Monte Carlo Empty tile — shared operator

シーンを選択し、$T$ を調整します。ハイライトされたタイルのみが解演算子を推定する必要があり、空のタイルはすべて一度計算された単一の閉形式演算子を共有します。

解演算子推定の局所性。 私たちの手法は、ジオメトリの近くの領域でのみ解演算子の推定を必要とすることで、グリッドベースアプローチの局所性を継承しています。その結果、実際のモンテカルロコストは、ドメインサイズではなく幾何学的複雑さに比例してスケールします。

もう一つ素晴らしい点は、私たちの手法が、解演算子の確率的モンテカルロ推定(各個々のタイル内で高度に並列化可能)のコストと、インターフェイス上の決定論的グローバルソルブのコストとの間で調整可能なトレードオフを明らかにすることです。以下のインタラクティブな図で見られるように、固定出力解像度 $N$ では、タイルのサイズ $B$ を大きくするとタイルあたりのモンテカルロ労力が増加しますが、結合されるインターフェイスが少なくなり、間隔が広がるため、決定論的グローバルソルブは安価になります。言い換えれば、$O(N^2)$ の自由度を持つグローバルソルブを、$O(N^2/B)$ の自由度に直接償却できます。より多くのモンテカルロコストを許容できる場合(自由度の数だけでなく、行列のスパース性や条件数も重要であると主張するかもしれません。実際、私たちの行列は隣接するインターフェイスのみを結合するためスパースです。つまり、システムのグローバル接続性は、各インターフェイス間接続がタイルあたりの離散化パラメータ $B$ に比例する複数の「遷移エッジ」を運ぶ可能性があることを除けば、有限差分システムに非常に似ています。もう一つの微妙な点は、私たちの行列は非対称であり、論文のセクション8で説明および議論していることです)。これは重要な結果であり、モンテカルロは非常に並列化可能で、アクセラレーテッドハードウェア(例:GPU)で実行できるため、将来的にはこれを基盤として構築できることを願っています(ここで言っていないのは、サンプル数だけでなくメモリにもコストがかかるということです!タイルが大きいほどメモリ使用量が増え、実際かなりの量になります!しかし、論文で議論しているように、私たちのコミュニティは、この問題を緩和するための多くの隣接ツールを開発してきたと信じており、私または他の誰かが将来それらを検討してくれることを願っています)。

固定 $N$ におけるインターフェイス値。タイルインターフェイスはグローバルソルブの唯一の未知数です。

Subtile resolution $B$ System size $N^2 / B$

サブタイル解像度 $B$ の関数としての決定論的グローバルソルブのシステムサイズ。

Subtile resolution $B$ = 4  ·  Tiles per axis $T = N/B$ = 16  ·  Global-solve DoFs $\approx N^2/B$ = 1024

Grid-like ($T{=}N$, $B{=}1$) Pure operator ($T{=}1$, $B{=}N$)

ローカルモンテカルロとグローバルソルブのトレードオフ。 固定出力解像度 $N$ では、$B$ を1から$N$までスライドさせることで、グローバルソルブがすべての $O(N^2)$ の自由度を持つグリッドライクなレジームと、グローバルソルブが自明 ($O(1)$) であるがすべてのタイルが完全に表計算された内部演算子を必要とする純粋な解演算子レジームの間を連続的に補間します。

8 反省と今後の研究

私は私たちの仕事と、それが将来の研究に開く扉に非常に興奮しています。人々がよく持ち出すことの一つは、レンダリングにおけるラジオシティやモンテカルロパストレーシングとの類推です(実際、私たちの手法は以前のレンダリング作業、特にボリュームレンダリングとの関連性がさらにあります。例えばこれらの作品を参照してください)。かつて、レンダリングに有限要素法が使われ、ノイズのためにモンテカルロ法を採用することに非常に消極的だった時代がありました。

この文脈で、Peter Shirleyは1997年のメールスレッドで有名にこう言いました。

要約すると、純粋なMCPTには利点が2つしかない — それは非常に単純なので大きなシーンにヒットしない、そして実装が容易であることだ。[…]

私の考えでは、解決策はハイブリッド手法 — バイアスを追加することだ!(MC界では冒涜だ :^)))。MC手法の良い部分を維持したい — それらは非常に堅牢で、正しく実装可能である — 私のMCコードは奇妙な調整されていない入力でクラッシュしない — ほとんどの非MC実装がそうであると、まっすぐに私に言ってほしい。しかし、結果がノイズが多いというのは正しい!!!バイアスを適切な方法で追加すれば、これらの利点を維持し、ノイズを減らすことができる(それがどのような方法かは知らないが)。

ここで強調したいのは、Peter Shirleyが正しかったということです。採用されるためには、モンテカルロ法には「ハイブリッド手法」が必要でした。そしてその解決策はデノイジングでした!デノイジングなしでは、既存の視覚効果やアニメーション映画はパストレーシングされなかったでしょう!人々はそれのためにアカデミー賞を受賞することさえありました。

では、古典的な数値手法と競争するためには、モンテカルロPDEソルバーもハイブリッドアプローチを必要とするのでしょうか?おそらくはい!しかし、デノイジングが正しい答えなのでしょうか?おそらくそうではありません。

私たちの論文では、異なるルートを取り、グリッドフリーモンテカルロ法とグリッドベースソルバーを調和させようとします。このプロジェクトで学んだことの一つは、グリッドベース手法が非常にうまく機能することです。収束を望むなら、それらを打ち負かすことはできません!そしてそれは驚くことではありません。数値解析をやっている人に尋ねれば、彼らは何かのようなことを言うでしょう。

モンテカルロは非常に悪い手法であり、他のすべての代替手法がより悪い場合にのみ使用されるべきである。

私の考えはこうです。グリッドベース手法のよく知られた利点(例:強力で高速な収束保証)を可能な限り活用し、グリッドベース手法が最も苦労する場所(例:複雑な形状)でグリッドフリーモンテカルロを導入することです。

とはいえ、まだ道のりは長いです。他のPDEや境界条件への一般化、より良い離散化スキーム、専用のグローバルソルバー、改善されたモンテカルロ推定器などです。私たちはそれに取り組んでいることを保証します…

References