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

• Item type: Trans(1)
• 公開日: 2014-08-19
• タイトル: 再直交化付きブロック逆反復法による固有ベクトルの並列計算
• タイトル / 言語: en
• タイトル: Reorthogonalized Block Inverse Iteration Algorithm for Parallel Computation of Eigenvectors
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: [数値アルゴリズム] 固有ベクトル計算，逆反復法，同時逆反復法，再直交化，マルチコア計算
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: 京都大学大学院情報学研究科／日本学術振興会特別研究員（DC1）
• 著者所属: 京都大学大学院情報学研究科
• 著者所属: 京都大学大学院情報学研究科
• 著者所属(英): en
• 著者所属(英): Graduate School of Informatics, Kyoto University / Research Fellow of Japan Society for the Promotion of Science (DC1)
• 著者所属(英): en
• 著者所属(英): Graduate School of Informatics, Kyoto University
• 著者所属(英): en
• 著者所属(英): Graduate School of Informatics, Kyoto University
• 著者名: 石上, 裕之; 木村, 欣司; 中村, 佳正
• 著者名(英): Hiroyuki, Ishigami; Kinji, Kimura; Yoshimasa, Nakamura
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 本論文では，並列計算機向けの実対称3重対角行列の固有ベクトル計算アルゴリズムとして再直交化付きブロック逆反復法を提案する．逆反復法による固有ベクトル計算における再直交化計算では，従来，ベクトル演算や行列-ベクトル乗算といった並列化粒度の比較的小さい演算を用いたアルゴリズムが中心であった．また，逆反復法の改良アルゴリズムとしてMultiple Relatively Robust Representation（MRRR）法が提案されているが，計算対象の行列の固有値分布によっては，固有ベクトルの直交性が失われてしまうことが知られている．本論文で提案する再直交化付きブロック逆反復法は，行列乗算中心の実装が可能な同時逆反復法を基にした，大粒度の並列性を持つアルゴリズムである．さらに，提案アルゴリズムにより，MRRR法で計算が破綻してしまうような固有ベクトルを行列乗算を用いて再計算することも可能になる．共有メモリマルチコアプロセッサシステム上での数値実験において，提案アルゴリズムにより，逆反復法や同時逆反復法と同等の計算精度が達成され，より高速な並列計算が実現されることを示す．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: 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.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11833852
• 書誌情報: 情報処理学会論文誌コンピューティングシステム（ACS）; 巻 7, 号 3, p. 1-12, 発行日 2014-08-19
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7829
• 出版者 / 言語: ja
• 出版者: 情報処理学会