A New High Performance and Scalable SVD algorithm on Distributed Memory Systems

This paper introduces a high performance implementation of $\mathtt{\text{Zolo-SVD}}$ algorithm on distributed memory systems, which is based on the polar decomposition (PD) algorithm via the Zolotarev’s function ($\mathtt{\text{Zolo-PD}}$), originally proposed by Nakatsukasa and Freund [SIAM Review, 2016]. Our implementation highly relies on the routines of ScaLAPACK and therefore it is portable. Compared with the other PD algorithms such as the QR-based dynamically weighted Halley method ($\mathtt{\text{QDWH-PD}}$), $\mathtt{\text{Zolo-PD}}$ is naturally parallelizable and has better scalability though performs more floating-point operations. When using many processes, $\mathtt{\text{Zolo-PD}}$ is usually 1.20 times faster than $\mathtt{\text{QDWH-PD}}$ algorithm, and $\mathtt{\text{Zolo-SVD}}$ can be about two times faster than the ScaLAPACK routine $\mathtt{\text{PDGESVD}}$. These numerical experiments are performed on Tianhe-2 supercomputer, one of the fastest supercomputers in the world, and the tested matrices include some sparse matrices from particular applications and some randomly generated dense matrices with different dimensions. Our $\mathtt{\text{QDWH-SVD}}$ and $\mathtt{\text{Zolo-SVD}}$ implementations are freely available at https://github.com/shengguolsg/Zolo-SVD.