適応格子細分化（AMR）

なぜ格子を「一様に」細かくしないのか

衝撃波、燃焼面、重力崩壊、乱流の渦など、科学技術計算で興味の対象になる現象の多くは、空間のごく一部でだけ解が急激に変化します。ところが有限差分法や有限体積法で必要な格子解像度は、この最も急峻な部分で決まってしまいます。計算領域全体をその解像度の一様格子で覆うと、実際には滑らかで粗い格子でも十分な広大な領域まで、無駄に細かい格子点を持つことになります。3次元では格子間隔を半分にすると格子点数は8倍、しかも陽解法では時間刻みもCFL条件で半分になり、総計算量は16倍に膨らみます。

適応格子細分化（Adaptive Mesh Refinement, AMR）は、この無駄を断つ手法です。解が急変する領域だけを局所的に細かい格子（高レベル）で覆い、滑らかな領域は粗い格子（低レベル）のまま残します。しかも現象が移動すれば細密領域もそれを追って動的に張り替えます。基盤となる離散化は有限差分法・有限体積法そのもので、AMRはその上に「どこをどれだけ細かくするか」を動的に管理する層を載せた枠組みだと捉えると整理しやすくなります。

ブロック構造型と木構造型

AMRのデータ構造は大きく2系統に分かれます。両者は「細分化の単位」が根本的に異なります。

横にスクロール

ブロック構造型AMR（block-structured / patch-based、Berger–Oliger–Colella法）は、細分化を一定サイズの矩形パッチ（ブロック）の集合として管理します。まず粗い格子（レベル0）で解を進め、細分化が必要と判定されたセル群を矩形で覆うようにクラスタリングし、その矩形領域を細分化率（refinement ratio、通常2）で細かくしたレベル1のパッチを重ねます。同じ操作をレベル1の上にレベル2、と再帰的に積み上げます。各パッチは内部が構造格子なので、パッチ単位ではキャッシュ効率の良い規則的なループが書け、既存の一様格子ソルバーをほぼそのまま再利用できるのが強みです。

木構造型AMR（tree-based / cell-based）は、セルそのものを再帰的に分割します。2次元なら1セルを4分木（quadtree）で4つ、3次元なら8分木（octree）で8つの子セルに割り、細分化が要ればさらにその子を割る、という形で木構造を作ります。細分化の単位がセル1個なので、細密領域の形状を必要な範囲にぴったり合わせられ、ブロック単位で切り上げる無駄（過剰細分化）が出にくい反面、隣接関係が木の探索を要し、間接参照が増える傾向があります。

細分化基準と誤差指標

「どのセルを細分化するか」を決めるのが細分化基準（refinement criterion）で、AMRの精度と効率を直接左右します。方式は大きく2つに分かれます。

第一は、物理量の特徴に基づくヒューリスティックな指標です。密度や圧力の勾配（隣接セルとの差）、あるいは2階差分による曲率が閾値を超えたセルを細分化対象とします。実装が軽く物理的な直感に合う一方、閾値がケース依存で、なぜその値かを原理的に正当化しにくい弱点があります。

第二は、離散化誤差そのものを推定する誤差指標です。代表がRichardson外挿に基づく推定で、同じ領域を現在の格子で解いた結果と、2倍粗い格子（または2ステップ分の積分）で解いた結果を比較します。手法の打ち切り誤差の次数が既知なら、両者の差から局所打ち切り誤差の大きさを見積もれます。これを閾値と比較し、誤差が許容値を超える領域を細分化します。

Richardson外挿による局所誤差推定（概念、2次精度の例）

  誤差 τ ≈ | u_fine - u_coarse | / (2^p - 1)
    u_fine   : 現在の格子での解
    u_coarse : 2倍粗い格子での解
    p        : 手法の精度次数（2次精度なら p=2）

  τ が閾値を超えるセル → 細分化（レベルを上げる）
  τ が下限を下回る領域 → 粗視化（デリファイン、レベルを下げる）

レベル間の補間とフラックス整合

異なるレベルの格子は境界で接するため、そこを正しく結合しないと解が破綻します。ここがAMRの実装で最も繊細な部分です。

まず粗→細の受け渡しです。細かい格子は自分の外側にゴースト層（ハロ）を必要としますが、その一部は粗い格子の領域にかかります。ここは粗い格子の値を空間補間（prolongation）して埋めます。補間の次数が本体スキームの精度より低いと、細密領域の境界だけ精度が落ちて誤差の発生源になるため、スキームと整合した次数の補間が求められます。ゴースト層交換そのものの考え方は領域分割法のハロ通信と同型で、AMRではそこにレベル間補間が加わると理解すると見通しが良くなります。

逆に細→粗の受け渡しは平均化（restriction）です。細かい格子で更新された領域は、対応する粗いセルの値を細かいセルの平均で上書きし、細密解の情報を粗い階層へ反映します。この制限/補間の往復は、複数解像度を行き来する点でマルチグリッド法と発想を共有しますが、目的は誤差の減衰ではなくレベル間の解の一貫性維持にあります。

そして保存則を扱う（有限体積法の）AMRで決定的に重要なのがフラックス整合（flux matching / refluxing）です。有限体積法ではセル境界を通過するフラックスの収支でセル値を更新するため、質量・運動量・エネルギーが厳密に保存されます。ところがレベル境界では、粗いセルが計算したフラックスと、そこに接する複数の細かいセルが計算したフラックスの合計が一致しません。両者を放置すると、レベル境界を横切るたびに保存量が生成・消失し、衝撃波の速度がずれるといった致命的な誤差になります。

リフラックス（フラックス補正）の考え方

1. レベル境界で、粗いセル側の面フラックス F_coarse を記録する
2. 同じ面に接する細かいセル群のフラックス総和 ΣF_fine を記録する
   （細かい側はサブサイクルで複数回進むので時間積分して合算）
3. 差分 (ΣF_fine − F_coarse) を粗いセルに事後補正として加える
   → レベル境界を挟んだフラックスの不一致を打ち消し、
     全体として保存則を厳密に満たす

負荷分散との相互作用

AMRの細密領域は現象を追って時々刻々と移動し、しかも高レベルほど時間ステップ数が多いため、計算負荷は空間的にも時間的にも激しく偏ります。一様格子なら領域を等分するだけで済む負荷分散が、AMRでは本質的に動的な問題になります。

各セルの作業コストはレベルごとに異なる（高レベルはサブサイクルの分だけ重い）ため、単純なセル数の等分では均等になりません。実務では各セルにレベル依存の重みを与え、空間充填曲線（モートン順序・ヒルベルト曲線）で全セルを1次元に並べて重みの累積和を等分する方式が広く使われます。木構造型AMRは8分木の走査順が自然にモートン順序と一致するため、この分割と特に相性が良いのが利点です。

まとめ

• AMRは解が急変する領域だけを高レベルの細かい格子で覆い、滑らかな領域を粗いまま残すことで、一様細密格子に対し計算量とメモリを桁で削減する枠組み。
• データ構造はブロック構造型（矩形パッチで構造格子ソルバーを流用）と木構造型（8分木/4分木でセル単位に密着）に大別され、それぞれ再利用性と形状適合性のどちらを取るかで住み分ける。
• 細分化基準は勾配・曲率のヒューリスティックとRichardson外挿による誤差指標があり、細分化と粗視化をヒステリシス付きで対に設計し、2:1バランスを保つのが実装の要点。
• レベル間は補間と平均化で結合し、有限体積AMRではフラックス整合（refluxing）で保存則を厳密に守る必要がある。動く細密領域はレベル依存重みと空間充填曲線による動的負荷分散と密結合する。