記号コレスキー分解

数値解析の数学的サブフィールド において、記号コレスキー分解は、コレスキー分解またはその変形 を適用するときに対称スパース行列の因子の非ゼロパターンを決定するために使用されるアルゴリズムです。${\displaystyle L}$

アルゴリズム

を体 の要素を持つ疎対称正定値行列とし、これを として因数分解します 。 ${\displaystyle A=(a_{ij})\in \mathbb {K} ^{n\times n}}$ ${\displaystyle \mathbb {K} }$ ${\displaystyle A=LL^{T}\,}$

効率的なスパース因数分解を実装するには、数値計算を行う前に因数の非ゼロ構造を決定する必要があることが分かっています。アルゴリズムを記述するために、以下の表記法を用います。

• およびを、それぞれ行列AとLの列iとj (対角線の下のみ、対角要素を含む)の非ゼロパターンを表す集合とします。${\displaystyle {\mathcal {A}}_{i}}$ ${\displaystyle {\mathcal {L}}_{j}}$
• を の最小の要素としてみなします。${\displaystyle \min {\mathcal {L}}_{j}}$ ${\displaystyle {\mathcal {L}}_{j}}$
• 親関数を使用して、マトリックス内の消去ツリーを定義します。${\displaystyle \pi (i)\,\!}$

次のアルゴリズムは、Aの効率的な記号因数分解を行います 。

${\displaystyle {\begin{aligned}&\pi (i):=0~{\mbox{for all}}~i\\&{\mbox{For}}~i:=1~{\mbox{to}}~n\\&\qquad {\mathcal {L}}_{i}:={\mathcal {A}}_{i}\\&\qquad {\mbox{For all}}~j~{\mbox{such that}}~\pi (j)=i\\&\qquad \qquad {\mathcal {L}}_{i}:=({\mathcal {L}}_{i}\cup {\mathcal {L}}_{j})\setminus \{j\}\\&\qquad \pi (i):=\min({\mathcal {L}}_{i}\setminus \{i\})\end{aligned}}}$