|
|
京都大学大学院 情報学研究科 中村佳正 教授
|
| |
行列の特異値計算、特異値分解は様々な情報処理、情報検索の基礎となる重要な線形数値演算です。
世界標準のパッケージライブラリとされるアメリカのLAPACK（レイパック）では、QR法という行列の固有値を求めるアルゴリズムに基づいて特異値と特異ベクトルを同時に計算するルーチンDBDSQR、
および、その分割統治版高速化であるDBDSDCが採用され、MATLAB、SLATECなど商用ソフトウェアに広く使われています。しかしこの方法は、特異値と特異ベクトルの同時計算を行うことに起因して計算量が多いため、
実用的な時間内で大規模行列の特異値分解を終えることが困難です。QR法は大規模行列の適切な特異値計算法とはいえませんが、現在のところ、
他に有力なアルゴリズムがないため特異値分解の商用ソフトウェアにおいて広く利用されています。
また、最近では、大規模行列の特異値を求めるために、新たな計算法が研究されていますが、
反復計算の収束を速めるための原点シフトにおいて、変数の正値性を壊さないようなシフト量の与え方が先験的には分からないため、
正値性が失われて精度が悪化したり、それを避けるため再計算を行ったりしています。直交性のよい特異ベクトル計算法も確立されてはおりません。
そこで戦略的創造研究推進事業のさきがけ「シミュレーション技術の革新と実用化基盤の構築」領域における中村教授のプロジェクトでは、 これらの問題を解決するために、新しい特異値計算・特異値分解法（I-SVD:
Integrable Singular Value Decomposition）の開発、改良、実装、並列化等の 研究開発を進めてきました。I-SVDでは、ある種の可積分な力学系の時間パラメータを離散化することにより、減算と平方根演算なしに特異値の2乗に収束する数列を
与える漸化式を用いることで、従来法よりも短時間で特異値計算でき、その上、高精度な結果を得ることができます。このプロジェクトにおいて、 一層の高速化と高精度化の実現に取り組み、収束性と数値安定性が保証された原点シフト付きの新しい特異値計算法であるmdLVsアルゴリズムが開発されました。
このアルゴリズムの漸化式 |
 |
において、見かけ上は減算がありますが、シフト項θがあっても、
全ての変数の正値性は保たれます。原点シフトの大きさを最小固有値のジョンソン下界よりも小さく取れば、mdLVsアルゴリズムは丸め誤差があっても、
非常に高い相対精度をもって必ず特異値に収束することが数学的に証明されました。mdLVsアルゴリズムはDLVSルーチンとして実装されています。
|
さらに、同プロジェクトにおいて、高速で直交性の優れた特異ベクトル計算法である2重コレスキー分解法が開発されました。
QR法とは異なり特異値計算と特異ベクトル計算は分離されています。mdLVsアルゴリズムによる特異値計算と2重コレスキー分解法による特異ベクトル計算を接続して
O(N^2)の計算量の2重対角行列の特異値分解法I-SVDが完成しました。このアルゴリズムはDBDSLVルーチンとして実装されています。I-SVDの高速性は、QR法がO(N^3)、
分割統治法がO(N^2)〜O(N^3)であることと比較して、際立っています。
|
高速・高精度の新しい特異値分解アルゴリズムI-SVDは、線形代数演算に革新をもたらすだけでなく、
情報通信分野の実用化基盤、共通基礎研究として広範囲のシミュレーション技術に適用が可能です。例えば、特異ベクトルの直交性に優れた高速特異値分解法の出現により、
大規模な医療画像の実時間での統計処理が可能となり、従来、QR法では数日かかっていた診断が数時間で終わることが見込まれます。
また、動画像から画像中の物体の2次元形状を推定するなど、時系列画像から対象物体の立体形状を求める問題は様々な応用のある可視化の問題ですが、
高精度の特異値分解アルゴリズムは信頼性の高いマルチメディアデータの実現につながります。
I-SVDアルゴリズムにおける特異ベクトル計算は相互依存性がないため並列化が容易で、計算の一層の高速化に顕著な効果が期待できます。
並列化の実現により、リアルタイムで多数の信号分離を行う半導体チップの開発が可能になり、
これにより、次世代の無線電話や移動体通信において大きな技術革新がもたらされると考えられます。
|
