Parallelism of Double Divide and Conquer Algorithm for Singular Value Decomposition

T. Konda, H. Tsuboi, M. Takata, M. Iwasaki, and Y. Nakamura (Japan)


Parallel Computing, Singular Value Decomposition, Eigen value Decomposition, Numerical Algorithm, Linear Alge bra


This paper presents some numerical evaluations of parallel double Divide and Conquer for singular value decompo sition. For eigenvalue decomposition and singular value decomposition, double Divide and Conquer was recently proposed. It first computes eigen/singular values by a com pact version of Divide and Conquer. The corresponding eigen/singular vectors are then computed by twisted factor ization. The speed and accuracy of double Divide and Con quer are as good or even better than standard algorithms such as QR and the original Divide and Conquer. In ad dition, it is expected that double Divide and Conquer has great parallelism because each step is theoretically paral lel and heavy communication is not required. This paper numerically evaluates a parallel implementation of dDC with MPI on some large scale problems using a distributed memory architecture and a massively parallel super com puter, especially in terms of parallelism. It shows high scal ability and super linear speed–up is observed in some cases.

Important Links:

Go Back