A new algorithm for singular value decomposition and its parallelization

被引：20
作者：
Konda, Taro [1 ]
Nakamura, Yoshimasa [1 ,2 ]
机构：
[1] Kyoto Univ, Dept Appl Math & Phys, Grad Sch Informat, Sakyo Ku, Kyoto 6068501, Japan
[2] Japan Sci & Technol Agcy, SORST, Tokyo, Japan
来源：
PARALLEL COMPUTING | 2009年 / 35卷 / 06期
关键词：
Singular value decomposition; Eigenvalue decomposition; Divide and Conquer; Twisted factorization; High performance computing; CONQUER ALGORITHM; DIVIDE;
D O I：
10.1016/j.parco.2009.02.001
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
An algorithm mainly consisting of a part of Divide and Conquer and the twisted factorization is proposed for bidiagonal SVD. The algorithm costs O(n(2))flops and is highly parallelizable when singular values are isolated. If strong clusters exist, the singular vector computation needs reorthgonalization. In such case, the cost of the algorithm increases to O(n(2) + nk(2)) flops and the parallelism may worsen depending on the distribution of singular values. Here k is the size of the largest cluster. The algorithm needs only O(n) working memory for every type of matrices. (C) 2009 Elsevier B.V. All rights reserved.
引用
收藏
页码：331 / 344
页数：14
相关论文
共 26 条
[1]  
[Anonymous], 1997, Applied Numerical Linear Algebra
[2]  
[Anonymous], 1965, SIAM J. Numer. Anal, DOI DOI 10.1137/0702016
[3]  
[Anonymous], 1995, LAPACK Users' Guide
[4]   A parallel eigensolver for dense symmetric matrices based on multiple relatively robust representations [J].
Bientinesi, P ;
Dhillon, IS ;
Van de Geijn, RA .
SIAM JOURNAL ON SCIENTIFIC COMPUTING, 2005, 27 (01) :43-66
[5]  
Blackford L., 1997, ScaLAPACK Users Guide
[6]  
CUPPEN JJM, 1981, NUMER MATH, V36, P177, DOI 10.1007/BF01396757
[7]   ACCURATE SINGULAR-VALUES OF BIDIAGONAL MATRICES [J].
DEMMEL, J ;
KAHAN, W .
SIAM JOURNAL ON SCIENTIFIC AND STATISTICAL COMPUTING, 1990, 11 (05) :873-912
[8]   Orthogonal eigenvectors and relative gaps [J].
Dhillon, IS ;
Parlett, BN .
SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS, 2003, 25 (03) :858-899
[9]   On computing an eigenvector of a tridiagonal matrix .1. Basic results [J].
Fernando, KV .
SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS, 1997, 18 (04) :1013-1034
[10]  
Gropp W., 1999, USING MPI
123