Preliminary Result of Parallel Double Divide and Conquer.
Taro Konda, Hiroaki Tsuboi, Masami Takata, Masashi Iwasaki, Yoshimasa Nakamura · 2006
Abstract This paper shows a concept for parallelization of double Divide and Conquer and its preliminary result. For singular value decomposition, double Divide and Conquer was recently proposed. It first computes singular values by a compact version of Divide and Conquer. The corresponding singular vectors are then computed by twisted factorization. The speed and accuracy of double Divide and Conquer are as well or even better than standard algorithms such as QR and 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 no required. However, any parallel model of double Divide and Conquer has not been studied yet. In this paper, policy of the parallelization is discussed. Then, a parallel implementation with MPI is tested on a distributed memory parallel computer. It successfully shows a high parallelism.