高速特異値分解のためのライブラリ開発

IPSJ Web Site 6 Citations 34 References

Bibliographic Information

Other Title
  • コウソク トクイチ ブンカイ ノ タメ ノ ライブラリ カイハツ
  • Implementation of Library for High Speed Singular Value Decomposition

Search this article

Abstract

高精度かつ高速に上2 重対角行列を特異値分解するために，我々は，dLV（離散ロトカ・ボルテラ：discrete Lotka-Volterra）系による新たな特異値分解ライブラリを開発している．既存ライブラリとしては，線形数値計算ライブラリLAPACK におけるDBDSQR がある．DBDSQR は，QRs法に基づいた特異値分解ライブラリであるが，計算量が多く，実行時間の面で大規模向きではない．また，いくつかの特異ベクトルのみを計算することも困難である．一方，dLV 系により定式化されたI-SVD（Integrable-Singular Value Decomposition）法は，計算量が抑えられる動作原理を持つ．本論文では，I-SVD 法の実装ライブラリDBDSLV を開発し，実行時間と計算精度について，DBDSQR との比較数値実験を行う．精度を調べる際，真の特異値と特異ベクトルが判明している上2 重対角行列が必要となる．そこで，Golub-Kahan-Lanczos 法によるテスト行列作成法を用いる．実験の結果，DBDSLV は，DBDSQR よりも誤差の少ない特異値と特異ベクトルを非常に短い実行時間で計算されることが確認された．計算された特異ベクトルの直交性も同程度であり，再直交化を行えばDBDSQR を上回ることも分かった．

To perform SVD (Singular Value Decomposition) of bidiagonal matrices with high accuracy and high-speed, we develop a library by using the dLV (discrete Lotka-Volterra) system. Today’s standard routine for SVD is DBDSQR provided in LAPACK (Linear Algebra PACKage). Since the computation of SVD by DBDSQR is based on the QRs (QR with shift) algorithm, DBDSQR is slow in speed and is unsuitable for large scaled problems. It is also difficult to obtain only a few singular vectors by using DBDSQR. On the other hand, the I-SVD (Integrable-SVD) scheme based on the dLV system enables us to cut down the computational cost by separating the computation process of singular values and vectors. In this paper, for evaluation of computational time and accuracy, we implement the I-SVD scheme to a new routine named DBDSLV and compare it with DBDSQR. For a comparison of accuracy, we use a method for constructing a class of upper bidiagonal random test matrices having true singular values and vectors by means of the Golub-Kahan-Lanczos method. As experimental results, we confirmed that DBDSLV is faster and errors of singular values and vectors in DBDSLV are smaller than those in DBDSQR. Though the orthogonality of computed singular vectors in DBDSLV is in the same order as in DBDSQR, we found that DBDSLV has a better orthogonality through a reorthogonalization.

Journal

Citations (6)*help

See more

References(34)*help

See more

Related Projects

See more

Keywords

Details 詳細情報について

Report a problem

Back to top