T. Konda, M. Takata, M. Iwasaki, and Y. Nakamura (Japan)
Singular Value Decomposition, Numerical Algorithm, Nu merical Analysis, High Performance Computing, Paral lelization, Integrable System
This paper proposes a new singular value decomposition algorithm which can be fully parallelized. I–SVD algo rithm was recently proposed using the theory of integrable systems. It computes singular value decompositions much faster than standard algorithms such as QR and Divide and Conquer(D&C), and at the same accuracy level. However, we show that the parallelism of I–SVD is limited to singu lar vector computation only because it shows seriality in the case of singular value computation. Our concern is a fully parallelizable algorithm whose serial version is as fast and accurate as I–SVD. Compared to the original D&C, where most of the running time is consumed for vector updating during singular vector computation, our new algorithm first computes singular values by the “compact” D&C without computing singular vectors. Thus, the compact D&C is wholly faster than the original one. The corresponding sin gular vectors are then computed by twisted factorization. The algorithm has great parallelism because each step can be executed parallelly. Our new algorithm is numerically tested on some SVD computations. It is as fast as I–SVD and even much faster than the standard algorithms. Also, its accuracy is as good as that of the others.
Important Links:
Go Back
