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

1楕円形PDEと境界値問題 多くの現実世界の現象は、楕円形偏微分方程式（PDE）によって支配されています。熱伝導、静電場、経路計画、定常流などがこれに該当します。これらはしばしば境界値問題（BVP）として定式化され、ドメインの境界で値が指定され、内部のPDEの解が求められます。例えば、ディリクレ境界条件を持つラプラス方程式を考えてみましょう。 $$ egin{cases} \Delta u = 0 & \text{in } \Omega \\ u = g & \text{on } \partial\Omega_D \end{cases} \ 下のインタラクティブな図を操作して、これが何をするのか直感的に理解してみてください。 Brush value +1.00 −1 (cold)+1 (hot) Reset boundary Presets 外側の境界帯をクリックしてペイントすると、ディリクレ値 $g$ がペイントされます。内部は $\Delta u=0$ を満たします。ディリクレ問題。 正方形上のディリクレ境界条件を持つラプラス方程式を解く。 より複雑な形状や境界条件を考慮することで、物事をより面白くすることができます。例えば、ノイマン境界条件を持つ混合境界値問題を解くことに人々はしばしば関心を持っています（注：ゼロノイマン条件に限定します）。 $$ egin{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) Reset boundary Hide isolines Scene Boundary presets 以前と同様に、ディリクレ帯をクリックしてペイントしてください。内部の障害物（点線、灰色）は $\partial u/\partial n = 0$ を強制します—等値線はそれに直角に曲がります。混合問題。 外側の境界にペイントされたディリクレ値と、内部のゼロノイマン形状を持つラプラス方程式。 よく見ると、解は実際には「ピクセル化」されていることがわかります。これは、グリッド上で有限差分法を用いて計算されているためです。有限差分法は理解しやすく実装も容易ですが、複雑な形状にはあまりうまく対応できず、しばしば極端なグリッド細分化が必要になります。もう一つの一般的な代替手段は、有限要素法を使用することです。しかし、有限要素法は慎重なメッシュ生成を必要とし、これは複雑な形状の場合、特に困難で時間のかかるものになる可能性があります。 例えば、車の設計をしていて、デザインを少し変更するたびにメッシュを再生成しなければならないと想像してみてください。それは悪夢でしょう—そして実際、そうなのです！ 都市の周りの風。 このシーンには、複雑な形状を持つ何百もの建物が含まれています。私たちの手法は、ここで定常流線として視覚化されている風パターンへのそれらの影響を特徴づけています。 2グリッドフリーモンテカルロ法 幸いなことに、コンピュータグラフィックスコミュニティは最近、古いアイデアであるグリッドフリーモンテカルロ法を復活させました。このアプローチの根幹をなす標準的なアルゴリズムは、Walk on Spheres（WoS）アルゴリズムです。確率解析からの直感は、内部点 $x$ から開始してブラウン運動（連続的なランダムウォーク）をシミュレートした場合、最終的にランダムな場所 $Z_\tau$ で境界に到達するというものです。そのランダムな場所での境界条件の値の期待値 $\mathbb{E}[g(Z_\tau)]$ は、与えられたディリクレ問題の解と正確に一致します。 ▶ Drop particle ✕ Clear ブラウン運動とラプラス方程式。 粒子は内部点 $x$ から開始し、ランダムな境界位置 $Z_\tau$ で吸収されるまで拡散します。境界は $g$ によって色付けされており、$g(Z_\tau)$ の平均を取ることで $u(x)$ が回復します。各内部点に対してこれを独立に行うことで、全体の解が得られます。各点に対して数回のウォークを行うだけでは推定値はノイズが多くなりますが、平均を取る回数を増やすにつれて、分散は徐々に消滅し、下の図に示すように滑らかな調和解が現れます。 Refresh rate: 1 walks/frame slowfast ⏸ Pause ↻ Restart low $u$ high $u$ 各内部ピクセルは、独立したWalk-on-Spheres推定値 $u(x)=\mathbb{E}[g(Z_\tau)]$ を実行します。ピクセルあたりのウォーク数を増やすと、フィールドはノイズが少なくなり、調和解に近づきます。これは連続的に実行され、スライダーで速度を設定します。 Number of samples: 1 段階的なモンテカルロ推定値。 同じ正方形のディリクレ問題が、ここではモンテカルロ法で各ピクセルごとに解かれています。各ピクセルは多数のランダムウォークを平均化します。サンプル数が少ないと内部はノイズが多くなりますが、サンプル数が増えるにつれてノイズは徐々に消えていきます。 しかし、ブラウン運動のシミュレーションは計算コストが高く、しばしばバイアスがかかります（通常、固定時間ステップとオイラー・マルヤマ法などで離散化する必要があります）。Walk on Spheresアルゴリズムは、球面上でのブラウン運動の出口分布が正確に一様であることを観察することで、これを克服します。これにより、代わりに、各球体がドメインに内接し、収束を速くするために可能な限り大きく選択される球体の境界から次の球体へとホップすることができます（ウォークは正確に境界に到達できないため、境界の周りに薄い $\epsilon$ シェルを導入し、ウォークがそこに到達したときに吸収されるようにします）。プロセス全体は、下のインタラクティブな図に示されています。 ノイマン境界条件の場合、WoSの特別なバリアントであるWalk on Stars（WoSt）が存在することが判明しました（その名前が示すように、この方法はノイマン（反射）境界条件をより良く処理するために「スター」上を歩きます。下のインタラクティブな図からは、それほど明白ではありません。長方形の場合、角のため、星形ドメインは球のスライスのように見えます）。 PDEのためのモンテカルロ法についてさらに詳しく知りたい場合は、こちらに素晴らしいコースとリソースがあります。 Solver WoSt WoS Neumann obstacles: 10 Walk speed: 1.00× ε-shell: 1e−2 Avg steps: — Dirichlet (absorbing) Neumann (reflecting) Show jump positions Clean mode (animated segments) Walk-length histogram (log) Reset histogram クリックするとウォークが開始され、ヒストグラムを埋めるために多くのウォークがバックグラウンドで実行されます。 Walk on Spheres/Stars。 モンテカルロ法は、境界にヒットするまで球体（またはスター）をサンプリングすることで再帰的に進行します。ノイマン障害物が多いほど、ウォークは「閉じ込められ」、境界にヒットするのに時間がかかり、分散が高く収束が遅くなります。ヒストグラムはウォーク長の分布を示しており、ノイマン障害物が増えると右にシフトします。 モンテカルロ法は本当に魔法のようです！しかし、上のインタラクティブな図を操作するとわかるように、ランダムウォークは境界にヒットする前に多くのステップを要します。これは、複雑な形状やノイマン優位の境界を持つ問題では特に顕著です（私たちの原稿では、図1の倉庫、図4の都市、図15の迷路など、これらの例の多くを紹介しています）。主な結果は分散と収束の遅さであり、信頼性の高い解が必要なシナリオでは実用的でなくなります（そして、これが人々がこれらの方法を実際に応用することに躊躇してきた理由かもしれません）。 私たちの研究では、この問題に2つの補完的な方法で取り組みました（多くの方法で解決されてきた問題であり、私たちの主な貢献と新規性は、モンテカルロ推定値の効率を単に改善したり、解をキャッシュしたりするのではなく、グリッドフリーモンテカルロ法を決定論的なグリッドベースソルバーと接続し、後者の優れた特性を活用する方法を提案することです）。第一に、図に示すように、ドメインをより小さなサブドメインに分割することでウォークを短くすることができます。第二に、後で導入されるように、決定論的なソルバーですべてのサブドメインを結合することにより、（制御可能な）離散化バイアスの代償を払って分散を「殺す」ことができ、決定論的なグリッドベース手法の優れた「分散フリー」特性を回復させます。 3分割統治法：より短いウォーク 問題が複雑な場合、自然な解決策はそれを分解することです。