分割統治法とツイスト分解法による新しい特異値分解アルゴリズム

情報処理学会 Web Site 参考文献36件

書誌事項

タイトル別名
  • ブンカツ トウチホウ ト ツイスト ブンカイホウ ニ ヨル アタラシイ トクイチ ブンカイ アルゴリズム
  • A New Singular Vaule Decomposition Algorithm by Divide and Conquer and Twisted Factorizations

この論文をさがす

抄録

本稿では高い並列性を持つ新しい特異値分解アルゴリズムを提案する．近年，ツイスト分解法を採用した固有値・特異値分解アルゴリズムが注目されている．これらは高速ではあるが，特異値計算部の逐次性などが原因で効率的に並列化されていない．そこで我々はこれらと同等の速度・精度に加え，優れた並列性の獲得を目指す．本稿で提案する新しいアルゴリズムは，まず“簡略化した” 分割統治法を利用し特異値のみを計算する．この簡略化は，計算時間の多くを費しうる行列演算のほとんどを省略する．次に特異値に対応する特異ベクトルをツイスト分解法により求める．これら各ステップはそれぞれ本質的に並列化可能であるため，このアルゴリズムは高い並列性を持つことが期待される．逐次アルゴリズムを実装し，特異値分布の異なる2 種類の行列の特異値分解で評価を行った．

This paper proposes a new singular value decomposition algorithm which can be effectivelly parallelized. For eigen/singular value decomposition, new algorithms with twisted factorization were recently developed. Althought these are fast, their parallelism are quite limited due to its seriality in the section of singular value computation. We concern a fully parallelizable algorithm which is in the same level as standard ones with respect to speed and accuracy. Our new algorithm first computes singular values by “compact” D&C, in which singular vectors are not computed. It can be faster than the original one because much of the running time is sometimes consumed for vector updating during singular vector computations. Secondly, the corresponding singular vectors are computed by twisted factorization. The algorithm has great parallelism because each step is executed parallelly. We numerically test it on some SVD computations.

収録刊行物

参考文献 (36)*注記

もっと見る

関連プロジェクト

もっと見る

キーワード

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

問題の指摘

ページトップへ