2.6 連立一次方程式の解法

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

(2-6-1)

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

(2-6-2)

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

(2-6-3)

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

(2-6-4)

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

(2-6-5)

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

(2-6-6)

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

(2-6-7)