A new algorithm for singular value decomposition and its parallelization
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) O ( n ) working memory for every type of matrices.
singular value decomposition divide and conquer twisted factorization eigenvalue decomposition high performance computing