3 入力データの疎性の利用

実用上現れる大規模SDP問題は，入力データに疎性があることが多い． すなわち，行列 $\mbox{\boldmath$A$}_i ~(i=0,1,\ldots,m)$が疎行列となる． 以後この行列を入力データ行列と呼ぶことにする． このような疎で大規模なSDP問題をなるべく 少ない計算時間とメモリ使用量で解くためには， 入力データ行列の疎性を活かした計算が不可欠となる． しかし，SDP問題に対する内点法の計算は LP問題に対するそれと比べ，疎性の利用が簡単ではない． その理由を一言で述べると， LP問題の非負制約は各変数に対し独立に働くが， SDP問題の半正定値制約は全ての変数に同時に影響を与えるため， 変数間の従属関係が強くなってしまうからである． その結果， 入力データ行列が疎であったとしても， 一般的に行列変数 $\mbox{\boldmath$X$}$やSchur方程式の係数行列 $\mbox{\boldmath$B$}$は密行列と なってしまう． すると，この密行列の保持に多くのメモリが必要となり， 密行列に関する演算（乗算・Cholesky分解・固有値分解など）に 多くの計算時間が必要となる．

以下の4つの節では，これらの密行列の取り扱いをなるべく回避し， できるだけ疎性を利用することにより，計算効率を上げる 手法について説明する． これらの手法は，同時に利用できるものもあるし， 組合せて利用できない場合もあることを，あらかじめ注意しておく．