Premium
Performance analysis and optimization of the parallel one‐sided block Jacobi SVD algorithm with dynamic ordering and variable blocking
Author(s) -
Kudo Shuhei,
Yamamoto Yusaku,
Bečka Martin,
Vajtersic Marian
Publication year - 2016
Publication title -
concurrency and computation: practice and experience
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.309
H-Index - 67
eISSN - 1532-0634
pISSN - 1532-0626
DOI - 10.1002/cpe.4059
Subject(s) - solver , speedup , computer science , parallel computing , block (permutation group theory) , singular value decomposition , convergence (economics) , variable (mathematics) , blocking (statistics) , algorithm , implementation , parallel algorithm , focus (optics) , supercomputer , mathematics , mathematical analysis , computer network , physics , geometry , economics , programming language , economic growth , optics
Summary The one‐sided block Jacobi (OSBJ) method is known to be an efficient method for computing the singular value decomposition on a parallel computer. In this paper, we focus on the most recent variant of the OSBJ method, the one with parallel dynamic ordering and variable blocking, and present both theoretical and experimental analyses of the algorithm. In the first part of the paper, we provide a detailed theoretical analysis of its convergence properties. In the second part, based on preliminary performance measurement on the Fujitsu FX10 and SGI Altix ICE parallel computers, we identify two performance bottlenecks of the algorithm and propose new implementations to resolve the problem. Experimental results show that they are effective and can achieve up to 1.8 and 1.4 times speedup of the total execution time on the FX10 and the Altix ICE, respectively. Comparison with the ScaLAPACK SVD routine PDGESVD shows that our OSBJ solver is efficient when solving small to medium sized problems ( n < 10000) using modest number ( < 100) of computing nodes. Copyright © 2016 John Wiley & Sons, Ltd.