第５回目となる今回の数理助教の会は, 数理第３研究室の相島健助さんに「行列の特異値計算」について発表していただきました. 相島さんは大規模行列の数値計算について, 精度評価や収束の理論的な解析, 新しい手法の提案を行っています. 今回の発表では特異値計算におけるdqds法について詳しく説明してもらいました.
特異値分解は行列の対角化と同様に線型代数で習う話ですが, 応用の場面ではかなりサイズの大きい行列について数値的に求めることになります. 例えば, デジカメ写真のような二次元画像は行列データで表現できますが, 特異値分解を行ってみると, 特異値の多くが十分小さくなるため0に近似できます. このような操作を施して画像に戻すと, 見た目はほとんど変わらずにデータ量が圧縮された画像ができるそうです. これ以外にもサイズの大きいデータを統計的に解析する場合に行列の特異値分解・固有値分解を高速に求める方法が非常に重要だそうです.
特異値分解の数値計算のアルゴリズム自体はすでに幾つかありますが, 相島さんの着目したのは次のような２ステップで特異値を求める方法です.
ステップ１では, 与えられた行列を有理演算と平方根の操作のみで上二重対角行列に変形します. こちらの操作は有限回で終了します. ステップ２では, ステップ１で作った上二重対角行列を特異値が対角成分に並んだ対角行列に変形します. この操作で特異値のすべてが求められます. しかし, ステップ２の操作は一般に有限回の反復では終了せず, 反復回数を増やすことで正しい値に近づけていきます.
ステップ２については, Fernando and Parlett (1994)がdqds法と呼ばれるアルゴリズムを提案しており, 現在，LAPACKなどの数値計算ライブラリで使われています. 反復回数を増やした時に正しい値に収束することは，Rutishauserにより別の反復アルゴリズム（LR法）の流れで間接的に証明されていましたが, 収束速度についての精緻な解析はなされていませんでした.
dqds法の収束速度は各ステップで設定されるシフトと呼ばれるパラメータに依存しており，いかに軽い計算量で（一反復の）収束を加速するシフト量を設定するかを考えるのが重要になります. そこで, 相島さんは, 既に知られているシフト量の設定の仕方（シフト戦略）での収束の速さの詳細な解析，新たなシフト戦略の提案などを行いました. さらに, 最近はdqds法を改良したアグレッシブデフレーション付dqds法を海外の研究者と共同で設計し, 既存のルーチンをさらに高速化しています.
大規模な行列計算を数値的に行う際には収束するだけでなく速さも重要だと改めて感じました. 個別の問題への応用だと, 行列や特異値に構造が入ってくるため, もっと高速化・簡略化できそうですね. そして, 今回は聞けなかったのですがやはり行列の固有値計算とそのアルゴリズムの速さに関する最近の研究も気になります.
数理第４研究室 助教 ＆さきがけ数学領域研究者（兼任）田中冬彦
0 件のコメント:
コメントを投稿