PARALLELISM OF DOUBLE DIVIDE AND CONQUER ALGORITHM FOR SINGULAR VALUE DECOMPOSITION

摘要

This paper presents some numerical evaluations of parallel double Divide and Conquer for singular value decomposition. For eigenvalue decomposition and singular value decomposition, double Divide and Conquer was recently proposed. It rst computes eigen/singular values by a compact version of Divide and Conquer. The corresponding eigen/singular vectors are then computed by twisted factorization. The speed and accuracy of double Divide and Conquer are as good or even better than standard algorithms such as QR and the original Divide and Conquer. In addition, it is expected that double Divide and Conquer has great parallelism because each step is theoretically parallel 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 computer, especially in terms of parallelism. It shows high scalability and super linear speed-up is observed in some cases.