再直交化付きブロック逆反復法による固有ベクトルの並列計算

情報処理学会 オープンアクセス

書誌事項

タイトル別名
  • Reorthogonalized Block Inverse Iteration Algorithm for Parallel Computation of Eigenvectors

この論文をさがす

説明

本論文では，並列計算機向けの実対称3重対角行列の固有ベクトル計算アルゴリズムとして再直交化付きブロック逆反復法を提案する．逆反復法による固有ベクトル計算における再直交化計算では，従来，ベクトル演算や行列-ベクトル乗算といった並列化粒度の比較的小さい演算を用いたアルゴリズムが中心であった．また，逆反復法の改良アルゴリズムとしてMultiple Relatively Robust Representation（MRRR）法が提案されているが，計算対象の行列の固有値分布によっては，固有ベクトルの直交性が失われてしまうことが知られている．本論文で提案する再直交化付きブロック逆反復法は，行列乗算中心の実装が可能な同時逆反復法を基にした，大粒度の並列性を持つアルゴリズムである．さらに，提案アルゴリズムにより，MRRR法で計算が破綻してしまうような固有ベクトルを行列乗算を用いて再計算することも可能になる．共有メモリマルチコアプロセッサシステム上での数値実験において，提案アルゴリズムにより，逆反復法や同時逆反復法と同等の計算精度が達成され，より高速な並列計算が実現されることを示す．

A reorthogonalized block inverse iteration algorithm is proposed for parallel computation of eigenvectors for symmetric tridiagonal matrices. The reorthogonalization process in the inverse iteration algorithm for computing eigenvectors is mainly based on the vector operations or the matrix-vector multiplications, whose parallel granularity is relatively small. Multiple Relatively Robust Representations (MRRR) algorithm is also proposed for computing eigenvectors, but the MRRR algorithm occasionally loses orthogonality. The proposed algorithm is derived from the simultaneous inverse iteration algorithm, which enables us to implement matrix-matrix multiplications and then has large parallel granularity. The proposed algorithm helps us to modify eigenvectors of the matrix, which the MRRR algorithm fails to compute with good orthogonality. Numerical experiments on shared memory multi-core processors show that the proposed algorithm achieves high accuracy as and is faster than both the inverse iteration algorithm and the simultaneous inverse iteration algorithm.

収録刊行物

関連プロジェクト

もっと見る

キーワード

詳細情報 詳細情報について

問題の指摘

ページトップへ