前処理（プリコンディショニング）

なぜ前処理が必要なのか ── 条件数が収束を決める

偏微分方程式を離散化すると、最終的には大規模疎行列 A に対する連立一次方程式 Ax = b を解く問題に帰着します。直接法（LU分解）はメモリ量が次元の増大に対して急激に増えるため、大規模問題では共役勾配法（CG）やGMRESなどの反復法が使われます。ところが反復法の収束速度は行列 A の条件数（condition number、κ(A) = 最大固有値 / 最小固有値）にほぼ支配されており、κ(A) が大きい（悪条件、ill-conditioned）と反復回数が爆発的に増えます。

対称正定値行列に共役勾配法を適用したときの誤差減少は、次のように条件数で評価できます。

CG法の収束レート（対称正定値行列の場合）

  ||e_k||_A / ||e_0||_A  ≦  2 * ( (√κ - 1) / (√κ + 1) )^k

  κ = κ(A) = λ_max / λ_min（条件数）
  k = 反復回数

  → κ が大きいほど収束比が1に近づき、同じ誤差まで落とすのに
    必要な反復回数 k がおよそ √κ に比例して増える

有限差分・有限要素で楕円型方程式（ポアソン方程式など）を離散化すると、格子間隔 h を細かくするほど κ(A) は 1/h^2 のオーダーで悪化します。つまり解像度を上げるほど反復法は遅くなるという構造的な問題があり、これを回避する手段が前処理です。

ヤコビ前処理・ILU前処理 ── 代数的なアプローチ

最も単純な前処理はヤコビ前処理（対角スケーリング）で、M を A の対角成分だけからなる行列にします。M^-1 の適用は対角成分の逆数を掛けるだけなのでコストはほぼゼロですが、条件数の改善効果は限定的です。対角成分のスケールが大きく異なる（成分間のスケールが不揃いな）行列には有効ですが、離散化由来の構造的な悪条件（格子を細かくするほど悪化する成分）にはほとんど効きません。

より強力なのが**不完全LU分解（ILU、Incomplete LU factorization）**です。通常のLU分解は疎行列であっても分解の過程でゼロだった要素が非ゼロに変化する現象（フィルイン、fill-in）が起き、メモリと計算量が膨張します。ILUはこのフィルインを許容パターンの範囲でわざと捨てることで、疎性を保ったまま近似的な L・U 因子を作ります。

ILU(0) の基本方針

  完全LU分解: A = LU（フィルインで密行列に近づく）
  ILU(0):     A ≈ L~U~ のみ計算し、
              元のAでゼロだった位置のフィルインは全て破棄

  → L~U~ の非ゼロパターンは A と同じに保たれる（メモリ増なし）
  → M = L~U~ として M^-1 を前進・後退代入で適用

ILU(0)より許容するフィルインのレベルを上げたILU(k)や、破棄する要素の絶対値に閾値を設けるILUT（threshold-based ILU）もあり、フィルインを増やすほど M が A に近づいて反復回数は減りますが、前処理の構築コストとメモリ、そして M^-1 適用（前進・後退代入）のコストが増えます。

ILU系の弱点は、前進・後退代入が本質的に逐次的な依存関係を持つため、並列化（特にGPUや多コア環境での並列前進代入）が難しい点です。この依存関係を緩めるため、行列をブロックごとに独立して分解するブロックヤコビ型ILUや、依存グラフをレベルごとに整理して並列度を引き出すレベルスケジューリングが実装上よく使われます。

多重格子前処理 ── メッシュ階層で低周波誤差を消す

ヤコビやILUのような代数的な前処理は、行列の局所的な構造だけを使うため、格子を細かくするほど悪化する低周波誤差（広い範囲にゆっくり変化する誤差成分）をなかなか減らせません。実はヤコビ法やガウス・ザイデル法などの単純な反復法（緩和法）は、高周波誤差（隣接格子点間で激しく振動する誤差）は数回の反復で急速に減衰させる一方、低周波誤差の減衰は極めて遅いという性質があります。

多重格子法（multigrid method）はこの性質を逆手に取り、複数の解像度の格子を往復することで低周波誤差も高周波として扱い直します。

V-サイクルの流れ（2水準の場合の概念）

  1. 細かい格子で緩和法を数回適用 → 高周波誤差を除去（平滑化, smoothing）
  2. 残った誤差方程式を粗い格子に制限（restriction）
     → 細かい格子での低周波誤差が、粗い格子では相対的に高周波になる
  3. 粗い格子で誤差方程式を解く（さらに粗い格子への再帰、または直接解く）
  4. 粗い格子の解を細かい格子に補間（prolongation）して補正
  5. 細かい格子で再度緩和法を適用（後平滑化）

格子構造を直接使う幾何マルチグリッド（geometric multigrid）は離散化格子が明示的に必要ですが、行列の係数だけから粗い階層を代数的に構成する**代数的マルチグリッド（AMG、Algebraic MultiGrid）**は非構造格子や複雑な形状の問題にも適用でき、汎用ソルバーの前処理として広く使われています。理想的な多重格子前処理では、反復回数が問題サイズNに依存せずほぼ一定に保たれ、全体の計算量がO(N)に近づきます。これはヤコビやILUのようにNの増大とともに反復回数が増える前処理とは質的に異なる強みです。

前処理コストと反復回数削減のトレードオフ

前処理を選ぶ際に見るべき指標は反復回数の削減幅だけではありません。総実行時間は次の関係で決まります。

総計算時間 ≈ 前処理の構築時間
            + 反復回数 × (1反復あたりの行列ベクトル積コスト
                          + 1反復あたりの前処理適用コスト)

ヤコビ前処理は反復回数の削減効果は小さいものの、1反復あたりのコストがほぼゼロで並列化も容易なため、GPU計算や超並列環境ではむしろ有利になる場合があります。逆にILUや多重格子は反復回数を大きく減らせても、前処理の構築・適用自体にコストと並列化の難しさを抱えます。したがって「収束が速い前処理」と「総実行時間が短い前処理」は必ずしも一致せず、問題の規模、利用可能な並列度、ハードウェア特性（メモリ帯域幅がボトルネックか、演算がボトルネックか）を踏まえて選定する必要があります。

まとめ

• 反復法の収束速度は行列の条件数κ(A)にほぼ支配され、離散化を細かくするほど条件数が悪化するため、前処理なしでは大規模問題ほど反復回数が増大する。
• 前処理は M^-1 A の固有値をクラスタ化させて条件数を下げる変換であり、Mが「Aに近く、かつ逆の適用が安い」ことが選定の核心。
• ヤコビ前処理は安価だが効果が限定的、ILUは疎性を保ちながらフィルインを制御して中〜大の効果を出すが逐次依存で並列化が難しい、多重格子は低周波誤差を階層間で消し理想的にはO(N)の計算量を達成するが楕円型問題に向き構築コストが高い。
• 前処理選定は反復回数削減だけでなく、構築・適用コストと並列性まで含めた総実行時間で評価する必要がある。