領域分割法（並列PDE計算）

なぜ「切るだけ」では並列化できないのか

偏微分方程式（PDE）を数値的に解く際、計算領域を格子に離散化し、各格子点の値を連立方程式として解きます。格子点数が数億〜数兆に達する問題は1台のプロセッサに収まらないため、計算領域を部分領域に切り分け、各プロセスへ割り当てる領域分割法が使われます。

見落としやすいのが、PDEの離散化（差分法・有限要素法・有限体積法いずれでも）では、ある格子点の更新に隣接する格子点の値が必要という点です。部分領域の境界付近を更新するには隣の部分領域の値が要るため、空間を切った瞬間にプロセス間通信が構造的に必須になります。

ゴースト（ハロ）交換

各プロセスは担当領域の周囲に、隣接プロセスの格子点のコピーを1〜数層だけ余分に保持します。これを**ゴースト層（ハロ）**と呼びます。ステンシル計算（隣接点を使う更新式）が参照する広さの分だけゴースト層を持てば、各プロセスは全体を持っているかのように更新できます。

各反復で:
  1. 内部格子点を更新する（隣接プロセスの値は不要）
  2. 通信: 自分の境界層を隣接プロセスへ送り、隣接プロセスの境界層を受け取る
  3. 境界に接する格子点を更新する（受け取ったゴースト層を参照）

手順1と2は依存関係がないため、内部点を計算している間に非同期通信を裏で進め、境界点の計算直前に完了を待つ計算と通信のオーバーラップが定石です。高次精度の差分ほど参照範囲が広がりゴースト層を厚くする必要があり、通信量は精度とのトレードオフになります。

シュワルツ法：分割してもなぜ同じ解に収束するのか

「部分領域ごとに計算した結果を境界で貼り合わせて、元の方程式の解と一致するのか」に理論的根拠を与えるのがシュワルツ法です。要点は部分領域を重ねること。オーバーラップ領域を持たせて分割し、各プロセスが並列に自領域を解き、境界条件に隣の前回反復の解を使う反復を繰り返します。反復を重ねるほどオーバーラップ部分の値が整合し、全体解に収束します。

実務ではシュワルツ法単体より、共役勾配法などクリロフ部分空間法の前処理として使うのが主流です。部分領域数（≒プロセス数）を増やしても反復回数が増えにくい前処理を設計できるかが、並列PDE計算のスケーラビリティを左右します。

負荷分散と通信オーバーヘッドのバランス

性能は次の2点のバランスで決まります。

• 負荷分散: 各プロセスの計算量（格子点数×コスト）を均等にする。
• 通信オーバーヘッド: 部分領域どうしの境界面積（交換するゴースト層の量）を小さくする。

格子が不均一だと単純な等分割では計算量が偏るため、格子点をグラフとみなして分割するパーティショニングが使われます。通信量は分割の形状にも依存し、同じ格子点数でも細長い短冊状より正方形・立方体に近い塊のほうが境界面積は小さく、表面積対体積比の問題として現れます。

2次元領域を N プロセスに分割する場合:
  1次元分割（短冊状）: 境界辺は左右2辺。1辺の長さは N によらず長いまま
  2次元分割（√N×√N）: 境界辺は最大4辺。1辺の長さは 1/√N で N を増やすほど縮む
  → N が大きい大規模計算ほど、2次元・3次元分割が有利

このため大規模計算では1次元分割ではなく2次元・3次元のブロック分割が好まれます。ただし分割次元を上げると隣接プロセス数（通信相手の数）が増えるため、通信の起動レイテンシが効いてくる小規模問題では、あえて分割数を絞ることもあります。

まとめ

• 領域分割法は隣接点依存のため、空間を切った瞬間にゴースト（ハロ）交換という通信を必然的に発生させる。
• シュワルツ法は部分領域を重ねて境界値を反復交換し、分割前の解への収束を理論的に保証する。加法的（並列向き）と乗法的（収束が速いが逐次的）にトレードオフがある。
• 性能は負荷分散と通信オーバーヘッド（表面積対体積比）のバランスで決まり、分割の次元・形状、強／弱スケーリングのどちらを狙うかで最適解が変わる。