特異値計算アルゴリズムdqds法およびm2dLVs法のための新しいシフト戦略

• 髙田, 雅美

• 豊川, 博己

• 石上, 裕之

• 木村, 欣司

• 山下, 巧

• 岩﨑, 雅史

• 中村, 佳正

Bibliographic Information

Other Title

• New Shift Strategy in the dqds Algorithm and the m2dLVs Algorithm for Singular Values

Abstract

本論文では，特異値計算アルゴリズムdqds法およびm2dLVs法の計算速度と相対精度を改善するために，新しいシフト戦略としてalgebraicシフトを提案する．従来，LAPACKに実装されたdqds法では経験則に基づくaggressiveシフトを，mdLVs法ではJohnsonシフトを採用している．aggressiveシフトは高速に計算されるが，無誤差計算でも過大なシフトとなる可能性がある．Johnsonシフトは，平方根計算を多用するため，速度面で適切とはいえない．よって，dqds法およびm2dLVs法の両方に対して，数学的理論に基づくalgebraicシフトを導入する．このシフト戦略の有効性を確認するために，従来のシフト戦略との比較を行う．

In this paper, we propose a new shift strategy “algebraic shift” in order to improve computational time and relative errors in the dqds and the m2dLVs algorithms for singular values. The dqds algorithm in LAPACK has adopted the aggressive shift, which is based on a rule of heuristics. The original mdLVs algorithm employs the Johnson shift. While the aggressive shift is quickly computed, it may be too large even in exact arithmetic. Since the Johnson shift requires a lot of square root, it is not suitable from the viewpoint of computational cost. Therefore, we introduce the algebraic shift, which is mathematically proved, into the dqds and the m2dLVs algorithms. In order to evaluate the resulting shift strategy, we compare it with the existing shift strategy.

Journal

• 情報処理学会論文誌コンピューティングシステム（ACS）

  情報処理学会論文誌コンピューティングシステム（ACS） 6 (3), 94-107, 2013-09-25

Keywords

• [数値アルゴリズム] 特異値計算，シフト戦略，algebraicシフト，dqds法，m2dLVs法，LAPACK 3.4.2

Details

• CRID: 1050564287856738176
• NII Article ID: 110009606663
• NII Book ID: AA11833852
• ISSN: 18827829
• Web Site: http://id.nii.ac.jp/1001/00095275/
• Text Lang: ja
• Article Type: article
• Data Source:
  • IRDB
  • CiNii Articles
  • KAKEN