2.7 連立一次方程式の解法

Aを複素数対称密行列、bを任意の複素数ベクトルとして以下の連立一次方程式を考えます。 行列の大きさをNとします。

(2-7-1)

対称密行列用の直接法として修正コレスキー法を考えます。
修正コレスキー法では行列を以下のように分解します。 ここでLは対角要素がすべて1の左下3角行列、Dは対角行列です。

(2-7-2)

式(2-7-2)のように分解するアルゴリズムは以下の通りです。ここでl,wは作業用の配列です。

(2-7-3)

式(2-7-3)で行列lは行列aで置き換えることが可能であり、 以下のように行列lは不要になります。

(2-7-4)

式(2-7-4)をさらに以下のように変形すると主要部がすべてjループ内に記述されます。
ここで、第3行(a_ii=0)はSIMDのパック演算が対角線にかかることの副作用を避けるためです。
演算量の大部分は第6行の総和が占め、N³/6回の積和演算が必要になります。
また必要メモリーは単精度のとき4N²バイトです。

(2-7-5)

以上でコレスキー分解(2-7-2)が完成したので、 これを式(2-7-1)に代入し、中間ベクトルyを介して以下の式で解くことができます。

(2-7-6)

式(2-7-6)はLが三角行列であることから、 次式のように前進代入と後退代入で解くことができます。
演算量はそれぞれN²/2回の積和演算です。

(2-7-7)