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

• Item type: Trans(1)
• 公開日: 2006-05-15
• タイトル: 分割統治法とツイスト分解法による新しい特異値分解アルゴリズム
• タイトル / 言語: en
• タイトル: A New Singular Vaule Decomposition Algorithm by Divide and Conquer and Twisted Factorizations
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: 数値アルゴリズム
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: 京都大学大学院情報学研究科
• 著者所属: 奈良女子大学大学院人間文化研究科
• 著者所属: 京都大学大学院情報学研究科，発展研究 科学技術振興機構
• 著者所属: 京都大学大学院情報学研究科，発展研究 科学技術振興機構
• 著者所属(英): en
• 著者所属(英): Graduate School of Infomatics, Kyoto University
• 著者所属(英): en
• 著者所属(英): Graduate School of Human Culture, Nara Women’s University
• 著者所属(英): en
• 著者所属(英): Graduate School of Infomatics, Kyoto University, SORST, JST
• 著者所属(英): en
• 著者所属(英): Graduate School of Infomatics, Kyoto University, SORST, JST
• 著者名: 誉田太朗; 高田, 雅美; 岩崎, 雅史; 中村, 佳正
• 著者名(英): Taro, Konda; Masami, Takata; Masashi, Iwasaki; Yoshimasa, Nakamura
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 本稿では高い並列性を持つ新しい特異値分解アルゴリズムを提案する．近年，ツイスト分解法を採用した固有値・特異値分解アルゴリズムが注目されている．これらは高速ではあるが，特異値計算部の逐次性などが原因で効率的に並列化されていない．そこで我々はこれらと同等の速度・精度に加え，優れた並列性の獲得を目指す．本稿で提案する新しいアルゴリズムは，まず“簡略化した” 分割統治法を利用し特異値のみを計算する．この簡略化は，計算時間の多くを費しうる行列演算のほとんどを省略する．次に特異値に対応する特異ベクトルをツイスト分解法により求める．これら各ステップはそれぞれ本質的に並列化可能であるため，このアルゴリズムは高い並列性を持つことが期待される．逐次アルゴリズムを実装し，特異値分布の異なる2 種類の行列の特異値分解で評価を行った．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: 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.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11833852
• 書誌情報: 情報処理学会論文誌コンピューティングシステム（ACS）; 巻 47, 号 SIG7(ACS14), p. 81-90, 発行日 2006-05-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7829
• 出版者 / 言語: ja
• 出版者: 情報処理学会