Vectorization of a Thread-Parallel Jacobi Singular Value Decomposition Method

DOI10.1137/22M1478847MaRDI QIDQ6097868zbMATH OpenOpenAlexFDO

Authors Vedran Novaković

Publication date 7 June 2023

Published in SIAM Journal on Scientific Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2202.08361

zbMATH Keywords

batched eigendecomposition of Hermitian matrices of order twoparallel one-sided Jacobi-type SVD methodSIMD vectorizationsingular value decomposition

Mathematics Subject Classification ID

Numerical computation of eigenvalues and eigenvectors of matrices (65F15) Orthogonalization in numerical linear algebra (65F25) Parallel numerical computation (65Y05) Numerical algorithms for specific classes of architectures (65Y10)

Abstract: The eigenvalue decomposition (EVD) of (a batch of) Hermitian matrices of order two has a role in many numerical algorithms, of which the one-sided Jacobi method for the singular value decomposition (SVD) is the prime example. In this paper the batched EVD is vectorized, with a vector-friendly data layout and the AVX-512 SIMD instructions of Intel CPUs, alongside other key components of a real and a complex OpenMP-parallel Jacobi-type SVD method, inspired by the sequential xGESVJ routines from LAPACK. These vectorized building blocks should be portable to other platforms that support similar vector operations. Unconditional numerical reproducibility is guaranteed for the batched EVD, sequential or threaded, and for the column transformations, that are, like the scaled dot-products, presently sequential but can be threaded if nested parallelism is desired. No avoidable overflow of the results can occur with the proposed EVD or the whole SVD. The measured accuracy of the proposed EVD often surpasses that of the xLAEV2 routines from LAPACK. While the batched EVD outperforms the matching sequence of xLAEV2 calls, speedup of the parallel SVD is modest but can be improved and is already beneficial with enough threads. Regardless of their number, the proposed SVD method gives identical results, but of somewhat lower accuracy than xGESVJ.

Recommendations

• A Parallel Algorithm for Computing the Singular Value Decomposition of a Matrix
• scientific article; zbMATH DE number 741117
• Computing the singular value decomposition on a distributed system of vector processors
• A parallel algorithm for computing the generalized singular value decomposition
• A relaxation scheme for increasing the parallelism in Jacobi-SVD
• A One-Sided Jacobi Algorithm for Computing the Singular Value Decomposition on a Vector Computer
• scientific article; zbMATH DE number 17435
• scientific article; zbMATH DE number 1206102
• An algorithm for the generalized singular value decomposition on massively parallel computers
• An efficient Jacobi-like algorithm for parallel eigenvalue computation

Cites work

• A GPU-based hyperbolic SVD algorithm
• A Hierarchically Blocked Jacobi SVD Algorithm for Single and Multiple Graphics Processing Units
• A Kogbetliantz-type algorithm for the hyperbolic SVD
• A One-Sided Jacobi Algorithm for Computing the Singular Value Decomposition on a Vector Computer
• A Set of Batched Basic Linear Algebra Subprograms and LAPACK Routines
• Algorithm 978: Safe scaling in the level 1 BLAS
• Batched computation of the singular value decompositions of order two by the AVX-512 vectorization
• Block recursive algorithm to generate Jacobi-sets
• Dynamic ordering for a parallel block-Jacobi SVD algorithm
• Implementation of Jacobi Rotations for Accurate Singular Value Computation in Floating Point Arithmetic
• Implementing High-performance Complex Matrix Multiplication via the 3m and 4m Methods
• Jacobi’s Method is More Accurate than QR
• LAPACK Users' Guide
• Linear algebra software for large-scale accelerated multicore computing
• Multiple representations to compute orthogonal eigenvectors of symmetric tridiagonal matrices
• New dynamic orderings for the parallel one-sided block-Jacobi SVD algorithm
• New Fast and Accurate Jacobi SVD Algorithm. I
• New Fast and Accurate Jacobi SVD Algorithm. II
• On the convergence of complex Jacobi methods
• On the Convergence of the Jacobi Method for Arbitrary Orderings
• Orthogonal Eigenvectors and Relative Gaps
• Solution of linear equations by diagonalization of coefficients matrix
• The LAPW method with eigendecomposition based on the Hari-Zimmermann generalized hyperbolic SVD
• The QR Transformation A Unitary Analogue to the LR Transformation--Part 1

Cited in

(5)

• A relaxation scheme for increasing the parallelism in Jacobi-SVD
• Batched computation of the singular value decompositions of order two by the AVX-512 vectorization
• Accurate complex Jacobi rotations
• Arithmetical enhancements of the Kogbetliantz method for the SVD of order two
• On convergence and accuracy of the J-Jacobi method under the de Rijk pivot strategy

This page was built for publication: Vectorization of a Thread-Parallel Jacobi Singular Value Decomposition Method

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6097868)