高精度特異値計算ルーチンの開発とその性能評価

IPSJ Web Site 4 Citations

Bibliographic Information

Other Title
  • コウセイド トクイチ ケイサン ルーチン ノ カイハツ ト ソノ セイノウ ヒョウカ
  • Implementation and Its Evaluations of Routine for Computing Singular Values with High Accuracy

Search this article

Abstract

高精度かつ高速に行列を特異値分解するために，我々は，dLV（離散ロトカ・ボルテラ：discrete Lotka-Volterra）系による新たな特異値分解ライブラリを開発している．この一環として，本論文では，特異値のみを計算するmdLVs（原点シフト付きmodified dLV）法の実装ならびに性能評価を行う．既存ルーチンとしては，線形数値計算ライブラリLAPACK におけるDBDSQR とDLASQがある．DBDSQR は，QRs 法に基づいた特異値分解ルーチンであるが，大規模特異値計算において計算速度，精度がともに十分でない．一方，DLASQ は，dqds 法に基づいた高速高精度な特異値計算ルーチンであるが，収束性が証明されていない．そのため，現在利用されている計算方法は，QRs法である．これらに比べ，mdLVs 法では，収束性が証明されており，DLASQ より速度では劣るものの，理論的には，同等以上の高精度性を持つ．本論文では，mdLVs 法を適用するために4 種類の実装手法を提案する．これらの手法の有効性を調べるために，複数のCPU を用いて実行時間と精度の比較実験を行う．その結果，mdLVs 法の理論どおりの高精度な性能を引き出す実装に成功した．

To perform singular value decomposition of matrices with high accuracy and high-speed, we develop a library by using the dLV (discrete Lotka-Volterra) system. In this paper, as a part of its development, we implement and evaluate the mdLVs (modified dLV with shift) algorithm for computing singular values only. The well-known routines for singular values are DBDSQR and DLASQ provided in LAPACK (Linear Algebra PACKage). Calculation of singular values using DBDSQR, which is based on the QRs (QR with shift) algorithm, is slow in speed and has low accuracy. DLASQ is based on the dqds (differential quotientdifference with shift) algorithm having high-speed and high accuracy. However, to the best of our knowledge, convergence to singular values has not been proved. Therefore, the most popular method is the QRs algorithm. In the mdLVs algorithm, convergence is guaranteed. Though the computational time of the mdLVs algorithm is not less than that of DLASQ, we can compute singular values by the mdLVs algorithm with numerical accuracy equal to or higher than that of the dqds algorithm. In this paper, we propose four methods for implementing the mdLVs algorithm. We apply these methods and experiment for performances both in computational time and errors using 5 kinds of CPUs. As results, we have succeed in realizing highly accurate ability of the mdLVs algorithm into full play.

Journal

Citations (4)*help

See more

Related Projects

See more

Keywords

Details 詳細情報について

Report a problem

Back to top