本節では,Schur行列の係数行列 の計算を 効率よく行う手法について説明する. は疎行列であっても, と は密行列となることに注意する.
(4)式の定義より,行列
は対称行列であるため,
行列の上半分のみ計算すればよい.
また,一行をまとめて計算すると効率的に計算ができる.
それを踏まえて,行列
の行目を計算する方法として,
以下で示した
,,という
3つの方法を提案した.
行列の行目を計算するとき, ,,の どれが最も計算量が少なくなるかは, 入力データ行列 の非ゼロ要素の数に依存する. また,行列の上半分のみを計算するため,最初に 個の入力データ行列を並べ替えると, 行列 全体の計算量は異なってくる. 幸いそれらの中で,浮動小数点演算の回数を最も少なくするやり方は, 入力データ行列の非ゼロ数の情報を元に, の計算量で知ることができる. 詳細については,[7]を参照されたい.
以上で説明した手法の一つの評価として, 各入力データ行列 に非ゼロ要素が高々 しかないような状態を考える. この場合,次のように計算量を減らすことができる.
元 | 新 | ||
係数行列 の計算 | |||
Schur方程式の求解 | |||
の計算 | |||
変数などの保持 | |||
係数行列 の保持 |