NR-SSOR right preconditioned RRGMRES for arbitrary singular systems and least squares problems

技術要約：非範囲対称系およびランク不足の長方形最小二乗問題のための NR-SSOR 右前処理 RRGMRES

問題の定義
一般化最小残差（GMRES）法は、線形系 $Ax = b$ に対する標準的なKrylov部分空間反復解法である。しかし、$A$ が特異であり、かつ系が不整合（すなわち $b \notin R(A)$）である場合、GMRESは、 $A$ が範囲対称（EP、すなわち $R(A) = R(A^T)$）でない限り、最小二乗（LS）解を提供することなく破綻することが知られている。具体的には、$R(A^T) \neq R(A)$ である場合（これは $A$ の指数が1以上であるケースを含む）、GMRESが失敗する初期ベクトル $x_0$ と右辺ベクトル $b$ が存在する。さらに、$A$ が範囲対称であっても、$b \notin R(A)$ である場合には、GMRES内で解かれる最小二乗部分問題が極めて悪条件になる可能性がある。

AB-GMRES法（$ABz=b$ にGMRESを適用する手法）のような既存のアプローチは、特異な系を扱うことができるが、前処理行列 $B$ の標準的な選択（例えば定常内反復を用いた $B=A^TC$）は、$A$ が範囲対称でない不整合な系に対して $AB$ が範囲対称であることを保証しないため、LS解を見つけることに失敗する可能性がある。

手法
著者らは、以下の3つの主要なコンポーネントを組み合わせた堅牢な反復法を提案している：

1. $B = CA^T$ による右前処理： $Ax=b$を直接解く代わりに、変換された最小二乗問題$\min_z |b - ABz|_2$を解く。ここで$B = CA^T$であり、$C \in \mathbb{R}^{n \times n}$ は対称正定値（SPD）行列である。この変換により、$A$ 自体が範囲対称であるかどうかにかかわらず、積 $AB = ACA^T$ は対称かつ範囲対称となる。その結果、本手法は任意の特異な $A$ と $b$ に対して、破綻することなくLS解 $x = CA^Tz$ を決定できる。
2. RRGMRES（範囲制限GMRES）： 不整合な系に固有の悪条件問題を解決するために、標準的なGMRESの代わりにRRGMRESを採用する。RRGMRESは探索空間を $A$ の値域（range）に制限することで、不整合な範囲対称系に対してより高い安定性を提供する。理論的解析によれば、RRGMRESにおけるヘッセンベルグ行列の最小特異値は下限を持つことが示されており、これは標準的なGMRESでは保証されない特性である。
3. NR-SSOR 前処理： 内反復右前処理として行列 $C$ を構築するために、非対称SSOR（NR-SSOR）法を用いる。著者らは、 $A$ にゼロ列が存在せず、緩和パラメータ $\omega$ が $0 < \omega < 2$ を満たす場合、得られる行列 $C$（NR-SSOR反復から導出される）が対称正定値（SPD）であることを証明した。この理論的保証により、提案されたフレームワークを、正方特異系および長方形ランク不足最小二乗問題（$A \in \mathbb{R}^{m \times n}$）の両方に適用できることが検証されている。

主な貢献

• 理論的正当化： NR-SSOR 右前処理 $B = CA^T$ について、標準的な条件下（$A$ にゼロ列がなく、$0 < \omega < 2$）で $C$ がSPDであることを証明した。これにより、$AB$ が範囲対称であることが保証され、非範囲対称系および長方形問題に対してLS解を堅牢に求めることが可能となる。
• 不整合な系に対する堅牢性： 提案された NR-SSOR 右前処理 RRGMRES は、指数が1以上で $R(A) \neq R(A^T)$ である場合を含む、任意の $b \in \mathbb{R}^m$ および特異な $A$ に対して最小二乗解を決定できることが示されている。
• 長方形問題への拡張： 本手法は、ランク不足の可能性がある大規模な長方形行列（Maragal, landmarkT, lp dfl001など）に対しても、低ランクの過決定および不足決定の長方形最小二乗問題へと正常に拡張されている。
• MINRES-QLP との比較： 特異な対称系を扱うことで知られる MINRES-QLP との比較枠組みを確立し、MINRES-QLP が一貫した系に対して最小ノルム解を見つけるのに対し、提案手法は不整合な系に対して優れた性能を提供することを指摘している。

数値実験の結果
以下の対象に対して広範な数値実験が行われた：

1. GP 不整合系： 指数1で $R(A) \cap N(A) = \{0\}$ だが $R(A) \neq R(A^T)$ である行列。
2. 指数2 不整合系： 指数が2である行列。
3. 不足決定最小二乗問題： 大規模な長方形行列（Maragal, landmarkT, lp dfl001）。

結果は以下を示している：

• 収束性： $Ax=b$ に直接適用された標準的な GMRES および RRGMRES は、これらの不整合な非範囲対称系に対して最小二乗解への収束に失敗することが多い。
• NR-SSOR の優位性： NR-SSOR 前処理 RRGMRES は、他の前処理（$B = \{ \text{diag}(A^TA) \}^{-1}A^T$ や $B = A^T$ など）と比較して、一貫して著しく小さい残差（多くの場合 $10^{-10}$ から $10^{-15}$）を達成する。
• 効率性： 提案手法は、無前処理または異なる前処理を用いたバリアントと比較して、少ない反復回数と大幅に少ない計算時間（特定の下決定問題において最大87.9倍高速）を必要とする。
• MINRES-QLP との比較： 不整合なシナリオにおいて、提案手法は MINRES-QLP よりも桁違いに小さい残差を達成し、より少ない反復回数でその最小値に到達した。

意義
本論文は、提案された NR-SSOR 右前処理 RRGMRES が、困難な線形代数問題のクラス、すなわち特異な非範囲対称系およびランク不足の長方形最小二乗問題に対して、理論的に正当化され、数値的に堅牢な解を提供することを主張している。NR-SSOR から導出される前処理行列 $C$ の正定値性を証明することで、著者らは、不整合な設定における標準的な GMRES に伴う破綻を回避することを保証している。数値実験は、このアプローチが理論的に妥当であるだけでなく、不整合な系における残差減少および計算速度の面で、AB-GMRES や MINRES-QLP などの既存の手法を凌駕する実用的な効率性を備えていることを検証している。