Concept in numerical linear algebra
数値線形代数 において 、 行列の 不完全 LU 分解 ( ILU と略される) は、 前処理 としてよく使用される LU 分解 のスパース 近似 です 。
導入 疎な線形システム を考えてみましょう。これは 、 L が 下一三角行列 、 U が 上三角行列 であるような の因数分解を計算することで解かれることがよくあります。 次に を解きます。これは 、 行列が三角行列であるため、効率的に行うことができます。 A x = b {\displaystyle Ax=b} A = L U {\displaystyle A=LU} L y = b {\displaystyle Ly=b} U x = y {\displaystyle Ux=y}
典型的な疎行列では、LU因子は元の行列よりもはるかに疎でなくなることがあります。これは 「フィルイン」と呼ばれる現象です。そのため、直接ソルバーを使用するために必要なメモリ量は、線形連立方程式を解く際のボトルネックとなる可能性があります。この問題に対処するには 、最小次数アルゴリズム など、行列の未知数のフィルインを削減する並べ替えを使用します 。
不完全因数分解では、 ではなく となる 三角行列 L , U を求めます。 を解くことは すぐに行えますが、 の正確な解は得られません 。そのため、代わりに 行列を 共役勾配法 や GMRES などの別の反復解法アルゴリズムの前処理として用います 。 A ≈ L U {\displaystyle A\approx LU} A = L U {\displaystyle A=LU} L U x = b {\displaystyle LUx=b} A x = b {\displaystyle Ax=b} M = L U {\displaystyle M=LU}
意味 与えられた行列に対して グラフを 次のように
定義する。 A ∈ R n × n {\displaystyle A\in \mathbb {R} ^{n\times n}} G ( A ) {\displaystyle G(A)}
G ( A ) := { ( i , j ) ∈ N 2 : A i j ≠ 0 } , {\displaystyle G(A):=\left\lbrace (i,j)\in \mathbb {N} ^{2}:A_{ij}\neq 0\right\rbrace \,,} これは、スパースパターンが 満たす必要の ある条件を定義するために使用されます。 S {\displaystyle S}
S ⊂ { 1 , … , n } 2 , { ( i , i ) : 1 ≤ i ≤ n } ⊂ S , G ( A ) ⊂ S . {\displaystyle S\subset \left\lbrace 1,\dots ,n\right\rbrace ^{2}\,,\quad \left\lbrace (i,i):1\leq i\leq n\right\rbrace \subset S\,,\quad G(A)\subset S\,.} 次の式が成り立つ 形の分解 A = L U − R {\displaystyle A=LU-R}
L ∈ R n × n {\displaystyle L\in \mathbb {R} ^{n\times n}} 下単位三角 行列 である U ∈ R n × n {\displaystyle U\in \mathbb {R} ^{n\times n}} 上三角 行列 である L , U {\displaystyle L,U} スパースパターンの外側ではゼロになります。 L i j = U i j = 0 ∀ ( i , j ) ∉ S {\displaystyle L_{ij}=U_{ij}=0\quad \forall \;(i,j)\notin S} R ∈ R n × n {\displaystyle R\in \mathbb {R} ^{n\times n}} スパースパターン内ではゼロです。 R i j = 0 ∀ ( i , j ) ∈ S {\displaystyle R_{ij}=0\quad \forall \;(i,j)\in S} は 不完全LU分解 と呼ばれます（スパースパターンに関して ）。 S {\displaystyle S}
L と U のスパースパターンは、元の行列 A のスパースパターンと同じになるよう選択されることが多い。基となる行列構造をコピーではなくポインタで参照できる場合、必要な追加メモリは L と U のエントリ分のみである 。この前処理はILU(0)と呼ばれる。
安定性 ILUの安定性に関しては、メイエリンクとファンデルフォルストによって次の定理が証明されました。 [1]
を M行列 とし、（完全な）LU分解を 、ILUを で与えると します 。 A {\displaystyle A} A = L ^ U ^ {\displaystyle A={\hat {L}}{\hat {U}}} A = L U − R {\displaystyle A=LU-R}
| L i j | ≤ | L ^ i j | ∀ i , j {\displaystyle |L_{ij}|\leq |{\hat {L}}_{ij}|\quad \forall \;i,j} が成り立つ。したがって、ILUは（完全な）LU分解と少なくとも同程度に安定である。
一般化 因数分解においてある程度の余分な充填を許容することで、より正確な前処理子を得ることができます。一般的な選択肢としては、行列 A の代わりに A 2 のスパースパターンを用いることです。この行列はA よりもかなり密ですが、全体としては依然としてスパースです。この前処理子はILU(1)と呼ばれます。この手順を一般化することができます。行列 A のILU(k)前処理子は、行列 A k+1 のスパースパターンを持つ不完全LU分解です 。
より高精度なILU前処理はより多くのメモリを必要とし、最終的には反復回数は減少するにもかかわらず、アルゴリズムの実行時間が増大します。したがって、ユーザーはコストと精度のトレードオフを評価する必要があり、通常は解くべき線形システムの族に応じてケースバイケースで評価する必要があります。
ILU分解の近似は、 高度に並列化された 固定小数点反復として実行することができる。 [2]
参照
参考文献 ^ Meijerink, JA; Vorst, Van Der; A, H. (1977). 「係数行列が対称π行列である線形システムの反復解法」. 計算数学 . 31 (137): 148– 162. doi : 10.1090/S0025-5718-1977-0438681-4 . ISSN 0025-5718. ^ Chow, Edmond; Patel, Aftab (2015). 「細粒度並列不完全LU分解」. SIAM Journal on Scientific Computing . 37 (2): C169-C193. doi :10.1137/140968896.
外部リンク
