LU分解の分散メモリ並列化について、雑然と考えてみたことをメモ。
LU分解の各プロセス毎の更新処理で参照することが必要受信データを、全て記憶して再利用する場合、行方向分散は上三角行列U、列方向分散は下三角行列Lを得ることができる。（上三角行列Uと下三角行列Lは誤差評価では必ずしも対称な扱いではない？＊櫻井鉄也・松尾宇泰・片桐孝洋：数値線形代数の数理とHPC、pp.13、2018）
外積形式ガウス法、行方向分散、ピボット選択で行が入れ替わる、ジャグ配列記憶、の場合、LU分解やピボット選択で行に対する処理を記述する際、(I)自プロセスが持たない行は空にしておいて処理区間を全部見て空かそうでないかを判定、(II)自プロセスの行インデックスが処理区間内に入っているか判定、を判定回数で比べてみる。(I)：n*(n+1)/2回、(II)：平均n*n/p（p：プロセス数）となってpがたった2を超えてしまれば(II)のほうが有利である。処理の記述が、(I)はシングルプロセスの書き方に近いが、(II)が並列化特有の書き方で、そもそも並列化を見据えるなら互換性は潔く捨ててよいということだ。内積形式ガウス法のLU分解は処理対象が全部の行に及ぶのと並列化不可能な順序依存になる部分もあるので、ここまで単純な話にならないかもしれない、未検討。
なお、(II)自プロセスの行インデックスが処理区間内に入っているか判定、の処理に必要な、行方向のインデックス向けの旧行番号（記憶位置）→新行番号の対応配列は、ピボット選択の際に、処理区間先頭にあたる新行番号を持つ行を探索しておき新しい枢軸行が持つ新行番号と入れ替える処理をすることで出来上がる。ただ、旧行番号（記憶位置）→新行番号の対応配列を使った処理は、外積形式ガウス法はともかく、更新の参照行が複数にわたる内積形式ガウス法では、検索の手間が増えるので難しいかもしれない。列方向のインデックス向けには処理が容易な新列番号→旧列番号の対応配列を使うならば、旧行番号（記憶位置）→新行番号の対応配列と照合することで、解は旧行番号（記憶位置）→旧列番号の対応に従って送りつけることになる。
もっとも、後退代入の処理内容からして全プロセスで受信して記憶しておけば送りつける処理も要らなくなるが、旧列番号→新列番号で解を参照できるような対応配列は何らかの形で用意しなければならない、あるいは受信時に新列番号→旧列番号の対応配列で所定位置に格納するか。旧列番号→新列番号の対応配列の用意が難しければ、係数の列方向も解も旧列番号で並ぶようにしておき、自分の新行番号（＝新列番号）と新列番号→旧列番号の対応配列を使って処理する。
LU分解・前進代入・後退代入はもともと一から順に処理するルーチンなので、入出力するデータ側を並び変えたいのか、ルーチン側を書き換えたいのか、どちらかを選ぶことになる。入力データ前処理有無の分岐は行の値交換でピボット選択の有無、出力データ後処理有無の分岐は列のピボット選択の有無、ルーチン側の書き換え有無は行と列のそれぞれインデックス交換の有無になるため、処理の分岐としては行と列でそれぞれ３パターン（ピボット選択なし、値交換でピボット選択、インデックス交換でピボット選択）あるように見える。
内積形式ガウス法のLU分解で考えてみる。第(k)列の更新処理は、(I)上三角行列U側を求める部分（前進代入と類似、逐次処理）、(II)下三角行列L側を求める部分（並列処理可能）、に分かれる。
行方向分散では、各プロセスが参照する要素＝(I)の更新後の第(k)列を送信する必要がある。
列方向分散では、各プロセスが計算した差分を(I)(II)の更新前の第(k)列が受信する必要がある。また、下三角行列L側の部分ピボット選択のための通信は不要である。
前進代入・後退代入の通信は、行方向分散では Broadcast、列方向分散では Send/Receive（定数ベクトルが別の場合は最初と最後で Scatter/Gather が加わる）
金田康正：並列数値処理、コロナ社、pp.56-60（2010）
LU分解ではないが、計算機特性により行方向分散と列方向分散のどちらが良いか変わるという面白い知見が得られている。
片桐孝洋、吉瀬謙二、本多弘樹、弓場敏嗣：データ再分散を行う並列Gram-Schmidt再直交化、情報処理学会論文誌コンピューティングシステム（ACS）、Vol.46, No.SIG6(ACS6)、pp.75-85（2004.05）（→PDF）
LU分解の各プロセス毎の更新処理で参照することが必要受信データを、全て記憶して再利用する場合、行方向分散は上三角行列U、列方向分散は下三角行列Lを得ることができる。（上三角行列Uと下三角行列Lは誤差評価では必ずしも対称な扱いではない？＊櫻井鉄也・松尾宇泰・片桐孝洋：数値線形代数の数理とHPC、pp.13、2018）
外積形式ガウス法、行方向分散、ピボット選択で行が入れ替わる、ジャグ配列記憶、の場合、LU分解やピボット選択で行に対する処理を記述する際、(I)自プロセスが持たない行は空にしておいて処理区間を全部見て空かそうでないかを判定、(II)自プロセスの行インデックスが処理区間内に入っているか判定、を判定回数で比べてみる。(I)：n*(n+1)/2回、(II)：平均n*n/p（p：プロセス数）となってpがたった2を超えてしまれば(II)のほうが有利である。処理の記述が、(I)はシングルプロセスの書き方に近いが、(II)が並列化特有の書き方で、そもそも並列化を見据えるなら互換性は潔く捨ててよいということだ。内積形式ガウス法のLU分解は処理対象が全部の行に及ぶのと並列化不可能な順序依存になる部分もあるので、ここまで単純な話にならないかもしれない、未検討。
なお、(II)自プロセスの行インデックスが処理区間内に入っているか判定、の処理に必要な、行方向のインデックス向けの旧行番号（記憶位置）→新行番号の対応配列は、ピボット選択の際に、処理区間先頭にあたる新行番号を持つ行を探索しておき新しい枢軸行が持つ新行番号と入れ替える処理をすることで出来上がる。ただ、旧行番号（記憶位置）→新行番号の対応配列を使った処理は、外積形式ガウス法はともかく、更新の参照行が複数にわたる内積形式ガウス法では、検索の手間が増えるので難しいかもしれない。列方向のインデックス向けには処理が容易な新列番号→旧列番号の対応配列を使うならば、旧行番号（記憶位置）→新行番号の対応配列と照合することで、解は旧行番号（記憶位置）→旧列番号の対応に従って送りつけることになる。
もっとも、後退代入の処理内容からして全プロセスで受信して記憶しておけば送りつける処理も要らなくなるが、旧列番号→新列番号で解を参照できるような対応配列は何らかの形で用意しなければならない、あるいは受信時に新列番号→旧列番号の対応配列で所定位置に格納するか。旧列番号→新列番号の対応配列の用意が難しければ、係数の列方向も解も旧列番号で並ぶようにしておき、自分の新行番号（＝新列番号）と新列番号→旧列番号の対応配列を使って処理する。
LU分解・前進代入・後退代入はもともと一から順に処理するルーチンなので、入出力するデータ側を並び変えたいのか、ルーチン側を書き換えたいのか、どちらかを選ぶことになる。入力データ前処理有無の分岐は行の値交換でピボット選択の有無、出力データ後処理有無の分岐は列のピボット選択の有無、ルーチン側の書き換え有無は行と列のそれぞれインデックス交換の有無になるため、処理の分岐としては行と列でそれぞれ３パターン（ピボット選択なし、値交換でピボット選択、インデックス交換でピボット選択）あるように見える。
内積形式ガウス法のLU分解で考えてみる。第(k)列の更新処理は、(I)上三角行列U側を求める部分（前進代入と類似、逐次処理）、(II)下三角行列L側を求める部分（並列処理可能）、に分かれる。
行方向分散では、各プロセスが参照する要素＝(I)の更新後の第(k)列を送信する必要がある。
列方向分散では、各プロセスが計算した差分を(I)(II)の更新前の第(k)列が受信する必要がある。また、下三角行列L側の部分ピボット選択のための通信は不要である。
前進代入・後退代入の通信は、行方向分散では Broadcast、列方向分散では Send/Receive（定数ベクトルが別の場合は最初と最後で Scatter/Gather が加わる）
金田康正：並列数値処理、コロナ社、pp.56-60（2010）
LU分解ではないが、計算機特性により行方向分散と列方向分散のどちらが良いか変わるという面白い知見が得られている。
片桐孝洋、吉瀬謙二、本多弘樹、弓場敏嗣：データ再分散を行う並列Gram-Schmidt再直交化、情報処理学会論文誌コンピューティングシステム（ACS）、Vol.46, No.SIG6(ACS6)、pp.75-85（2004.05）（→PDF）