LU分解 ピボット選択 交換 インデックス 値

Ax=bを解くため、LU分解：A=LUの後の、前進代入：Ly=b、後退代入：Ux=yの過程を考える。

LU分解中のピボット選択による並び替えは、値交換、アドレス交換、どちらのやり方かでA=LUの要素へのアクセス方法が変わる。b、y、xの要素のアクセス方法は、LU分解中のピボット選択による並び替えが値交換、アドレス交換、どちらのやり方かは関係しないが、前進代入を内積形式ガウス法でも使用する場合は、A=LUの要素へのアクセス方法とb、yの要素へのアクセス方法を揃えなければならない。

前進代入や後退代入の解yや解xは、新行番号＝新列番号で紐づけられた（旧行番号や旧列番号とは独立した）ただの入れ物になっている。旧行番号→新行番号の対応で並び替えた順（ピボット選択の並び替えの正順）で前進代入の解yが求まり、新行番号＝新列番号であるから並び替えずに後退代入の解xを求めれば、結果的に旧行番号→新列番号の対応で並び替えた順になっている（列について値を入れ替えようとインデックスを入れ替えようと、解は新行番号＝新列番号の順で解が求まっている）から、新列番号→旧列番号に対応させて並び替えた順（ピボット選択の並び替えの逆順）で最終的な解になる。繰り返し計算を考えたときにインデックスの意味合いを考えると、旧行番号・旧列番号のほうは係数、定数、解の読み書きの位置を表し、新行番号・新列番号のほうは処理の位置を表していることになる。

新行番号→旧行番号の対応配列を新列番号→旧列番号に対応させて並び替えた順（ピボット選択の並び替えの逆順）にすると、旧列番号→旧行番号の対応配列ができあがる。新列番号→旧列番号の対応配列から照合すれば、新行番号（＝新列番号）→旧行番号の対応が復元できる。旧行番号の位置に記憶させたままま処理をするならば、（前進代入と後退代入では照合で対応を復元させて）新行番号→旧行番号の対応配列を使った処理を記述し、（列については値を入れ替えようとインデックスを入れ替えようと、解は新列番号に等しい新行番号に対応した順で求まり旧行番号の位置に格納されるから、）最後の解は旧列番号→旧行番号の対応配列を使って読み取ることになる。
新列番号→旧列番号の対応配列を新行番号→旧行番号に対応させて並び替えた順（ピボット選択の並び替えの逆順）にすると、旧行番号→旧列番号の対応配列ができあがる。

前進代入と後退代入で連続アクセスとするためのデータ交換のコストは下記のようになる。（A=LUはジャグ配列）
A=LU（行の並び替え）：N*2回のアクセス向けに最大(N-1)回のポインタ値交換（※同じ行内なら、列の交換がなければ連続アクセスになる。）
A=LU（列の並び替え）：N*N回のアクセス向けに最大(N-1)*N回のデータ値交換
b、y、x：N*N回アクセス向けに最大(N-1)*2回のデータ値交換
※64ビット動作であれば、double型の値交換とsize_t型のポインタ値交換は、どちらも64ビット分の値を交換するのでコストは同じと思われる。

LU分解の時点で、A=LUの列の値交換を実現することを考えてみた。クラウト法と内積形式ガウス法では分解過程で参照または更新する領域で値交換を行っていくと全領域の交換が完了している。外積形式ガウス法では分解過程で参照または更新する領域で値交換するだけでは、分解過程で参照しなくなった上三角行列側に未交換となる領域が残ってしまう。外積形式ガウス法で値交換が終わっていない箇所の後処理は最大(N-1)*N回のデータ値交換となり、前進代入か後退代入で１回参照されるだけなので、A=LUが固定で、bを何回も変更して計算するような場面でないと恩恵がない。