行列の特異値分解の高速数値計算法に関する研究

点击翻译按钮获取中文摘要

行列の特異値は,データマイニングなどで重要な役割を果たし,特異値計算法の確立は,科学技術計算において大きな意義がある.行列の特異値計算では,まず直交変換により上二重対角行列に変換し,この上二重対角行列に対して反復計算を行って特異値を求める.上二重対角行列の特異値を求めるための有力なアルゴリズムがdqds(differential quotient difference with shifts)法であり,世界中で広く使われている線形計算ライブラリLAPACKにもDLASQルーチンという実装がある.本研究では,このdqds法の理論的収束性を明らかにし,それを基に高速化することを目指している.dqds法の高速化には,アルゴリズム中のシフト戦略とデフレーション戦略を改良するのが自然な方針と言える.昨年度までは主にシフト戦略の理論解析および改良を行ってきたが,本年度はそれを基にデフレーション戦略について考察し,新たにアグレッシブデフレーションというデフレーション戦略を導入することでより高速な特異値計算を実現した.アグレッシブデフレーションの概念そのものは古くから存在していたが,本研究では現代の洗練されたアルゴリズムにおいて効果的な実装を提案し,特に大規模行列に対して本手法によりアルゴリズムが高速化されることを数値データにより示し,その結果を裏付ける理論解析も行っている.また従来のdqds法では並列計算が原理的に実現し得なかったのであるが,本研究で提案したアグレッシブデフレーション付きdqds法では並列計算の可能性も視野に入るようになっており,今後の発展が期待される.また本研究で開発した新たなアグレッシブデフレーションは対称行列の固有値計算に用いられるQR法に対しても素直に導入可能であり,実際に効果的であることを数値実験により確認している.