3.1 疎性に基づく係数行列の計算

本節では，Schur行列の係数行列 $\mbox{\boldmath$B$}$の計算を 効率よく行う手法について説明する． $\mbox{\boldmath$A$}_{i}~(i=1,2,\ldots,m)$は疎行列であっても， $\mbox{\boldmath$X$}$と $\mbox{\boldmath$Z$}^{-1}$は密行列となることに注意する．

(4)式の定義より，行列 $\mbox{\boldmath$B$}$は対称行列であるため， 行列の上半分のみ計算すればよい． また，一行をまとめて計算すると効率的に計算ができる． それを踏まえて，行列 $\mbox{\boldmath$B$}$の$i$行目を計算する方法として， 以下で示した $\mathcal{F}_1$,$\mathcal{F}_2$,$\mathcal{F}_3$という 3つの方法を提案した．

$$\begin{array}{l} \begin{array}{llll} \mathcal{F}_1: \hspace*... ...\gamma\epsilon} & ~~~(j=i,i+1,\ldots,m) \end{array}\end{array}$$

行列の$i$行目を計算するとき， $\mathcal{F}_1$,$\mathcal{F}_2$,$\mathcal{F}_3$の どれが最も計算量が少なくなるかは， 入力データ行列 $\mbox{\boldmath$A$}_{i}~(i=1,2,\ldots,m)$の非ゼロ要素の数に依存する． また，行列の上半分のみを計算するため，最初に $m$個の入力データ行列を並べ替えると， 行列 $\mbox{\boldmath$B$}$全体の計算量は異なってくる． 幸いそれらの中で，浮動小数点演算の回数を最も少なくするやり方は， 入力データ行列の非ゼロ数の情報を元に， $\mathcal{O}(m \log m)$の計算量で知ることができる． 詳細については，[7]を参照されたい．

以上で説明した手法の一つの評価として， 各入力データ行列 $\mbox{\boldmath$A$}_i~(i=1,2,\ldots,m)$に非ゼロ要素が高々 $\mathcal{O}(1)$しかないような状態を考える． この場合，次のように計算量を減らすことができる．

	元		新
係数行列 $\mbox{\boldmath$B$}$の計算	$\mathcal{O}(n^3m+n^2m^2)$	$\Longrightarrow$	$\mathcal{O}(m^2)$
Schur方程式の求解	$\mathcal{O}(m^3)$
$\mbox{$d$\hspace{-0.21em}\mbox{\boldmath$X$}}'$の計算	$\mathcal{O}(n^3)$
変数などの保持	$\mathcal{O}(n^2)$
係数行列 $\mbox{\boldmath$B$}$の保持	$\mathcal{O}(m^2)$