An Efficient Batch Solver for the Singular Value Decomposition on GPUs CCS: Mathematics of computing Mathematical software performance CCS: Mathematics of computing Solvers CCS: Computing methodologies Parallel algorithms

Ahmad Abdelfattah, Massimiliano Fasi · 2026

Read An Efficient Batch Solver for the Singular Value Decomposition on GPUs CCS: Mathematics of computing Mathematical software performance CCS: Mathematics of computing Solvers CCS: Computing methodologies Parallel algorithms by Ahmad Abdelfattah, Massimiliano Fasi (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-17979.txt.

Introduction

Ahmad Abdelfattah and Massimiliano Fasi build a faster batch solver for a core matrix task on graphics chips. Their 2026 preprint deals with the singular value decomposition, or SVD. The SVD underpins tools like principal component analysis, low-rank fits, and randomized methods. Many jobs need not one SVD but thousands of small ones at once. That batch regime is where the authors aim.

Small problems behave unlike large ones on a GPU. Launch costs and memory moves can swamp the math. An efficient batch solver packs the work so the chip stays busy. Fast batch SVD speeds up data analysis, signal tools, and learning pipelines that call it again and again.

Catalog record

CREATORAhmad Abdelfattah, Massimiliano Fasi
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE77 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2601-17979

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

An Efficient Batch Solver for the Singular Value Decomposition on GPUs CCS: Mathematics of computing Mathematical software performance CCS: Mathematics of computing Solvers CCS: Computing methodologies Parallel algorithms Ahmad Abdelfattah, Massimiliano Fasi Abstract . The singular value decomposition (SVD) is a powerful tool in modern numerical linear algebra, which underpins computational methods such as principal component analysis (PCA), low-rank approximations, and randomized algorithms. Many practical scenarios require solving numerous small SVD problems, a regime generally referred to as batch SVD . Existing programming models can handle this efficiently on parallel CPU architectures, but high-performance solutions for GPUs remain immature. A GPU-oriented batch SVD solver is introduced. This solver exploits the one-sided Jacobi algorithm to exploit fine-grained parallelism, and a number of algorithmic and design optimizations achieve unmatched performance. Starting from a baseline solver, a sequence of optimizations is applied to obtain incremental performance gains. Numerical experiments show that the new solver is robust across problems with different numerical properties, matrix shapes, and arithmetic precisions. Performance benchmarks on both NVIDIA and AMD systems show significant performance speedups over vendor solutions as well as existing open-source solvers. 1. Computing the Singular Value Decomposition The singular value decomposition (SVD) is one of the most powerful and versatile tools in modern linear algebra. Its roots trace back to the work of classical mathematicians ( 66 ) , from James Sylvester (1814–1897), Eugenio Beltrami (1835–1899), and Camille Jordan (1838–1921) to Erhard Schmidt (1876-1959) and Hermann Weyl (1885–1955). In essence, the SVD constructs orthonormal bases for the row and column spaces of a matrix. These bases reveal rank information and can be used to construct optimal low-rank approximations, which are necessary in a wide range of applications. In numerical linear algebra, the singular values are used to estimate the effective rank ( 45 ) and the 2-norm condition number of a matrix A . In numerical algorithms, the SVD can be used to compute the Moore–Penrose pseudoinverse of a matrix ( 56 ; 62 ) , which can be used to solve linear least squares problems ( 63 ) and has been applied to the processing of images ( 15 ) as well as genomic data ( 14 ) . In data science and statistics, the geometric interpretation of the SVD underlies principal component analysis ( 61 ; 40 ; 43 ; 55 ) and other techniques that rely on understanding variance and structure in data ( 22 ) . Finally, Eckart and Young ( 34 ) have shown that truncating the SVD provides the best low-rank approximation to A . Such low-rank approximations are essential in dimensionality reduction and data compression techniques, and they play an important role in reducing the complexity of neural networks ( 27 ) and large language models ( 70 ) . A selection of other interesting applications can be found in the short survey by Martin and Porter ( 51 ) . Here, we focus on the reduced or economy-size SVD, which we now define. Every matrix A\in\mathbb{C}^{m\times n} can be written as (1) A=U\varSigma V^{H}, where U\in\mathbb{C}^{m\times\min(m,n)} and V\in\mathbb{C}^{n\times\min(m,n)} have orthonormal columns, \varSigma\in\mathbb{C}^{\min(m,n)\times\min(m,n)} is diagonal with non-negative real entries, and V^{H} denotes the conjugate transpose of V . The columns of U and V are the left singular vectors and right singular vectors of A , respectively, and the values along the diagonal of \varSigma are its singular values . The singular values often appear along the diagonal of \varSigma in descending order, so that \sigma_{1}\geq\sigma_{2}\geq\ldots\geq\sigma_{\min(m,n)}\geq 0. The SVD is tightly connected to the Hermitian eigenvalue problem, because (2) A^{H}A=V\varSigma U^{H}U\varSigma V^{H}=V\varSigma^{2}V^{H},\qquad AA^{H}=U\varSigma V^{H}V\varSigma U^{H}=U\varSigma^{2}U^{H}. In other words, the right and left singular vectors of A are the eigenvectors of the Gram matrices A^{H}A and AA^{H} , respectively. The two Gram matrices have the same eigenvalues, which are the squares of the singular values of A . This property is the algorithmic foundation of the efficient design introduced in this paper. In view of ( 2 ), computing the SVD can be reduced to the solution of a Hermitian eigenvalue problem: if we solve A^{H}A=V\varSigma^{2}V^{H} , then the relation AV=U\varSigma shows that the singular values of A are the norms of the columns of AV , and thus U can be recovered from the identity U=AV\varSigma^{-1} . Equivalently, we can solve the Hermitian eigenvalue problem AA^{H}=U\varSigma^{2}U^{H} and use the definition of the SVD to obtain V . In the literature, we can identify two main families of efficient and practical algorithms to compute the SVD. On the one hand, we have algorithms that reduce A to a simpler form. They usually perform three phases. (i) First , they reduce the input matrix A to a bi-diagonal form A=U_{0}BV_{0}^{H} . Computationally, this bi-diagonalization phase is usually the most expensive, and much effort has been dedicated to accelerating it on parallel architectures, including one-stage ( 47 ) and two-stage ( 48 ; 37 ) algorithms. (ii) Second , they use an SVD solver to compute U_{1} and V_{1} such that B=U_{1}\varSigma V_{1}^{H} . Unlike (i) , this second phase is an iterative process in general. Customary techniques for this diagonalization are the QR algorithm, the Divide and Conquer (D&C) algorithm, and the Multiple Relatively Robust Representations (MRRR) method. These iterative solvers are relatively lightweight, compared with the bi-diagonalization scheme. Most of them, however, are nontrivial to parallelize efficiently, especially on GPUs. (iii) Third , they compute the singular vectors of A as U=U_{0}U_{1} and V=V_{0}V_{1} . This final phase is only performed if the singular vectors are needed. Computationally, this only requires matrix multiplications, which are highly optimized on all parallel architectures. In view of (i) , all techniques that follow this idea are collectively known as bi-diagonalization algorithms . The alternative is to use Jacobi-type algorithms , which are based on the Jacobi solver for Hermitian eigenproblems. In contrast to bi-diagonalization algorithms, Jacobi methods operate directly on A and do not require the preprocessing step to reduce it to bi-diagonal form. There are two standard routes to compute the SVD using Jacobi-type algorithms: • the two-sided approach, which applies plane rotations on both sides of A until it is diagonalized; and • the one-sided approach, which implicitly diagonalizes the Hermitian matrix A^{H}A without explicitly forming it. Jacobi algorithms are often slower than those based on bi-diagonalization, because they require substantially more floating point operations (FLOPs) than the alternatives mentioned above ( 26 , sect. 5.3) . However, there has been a resurgence of interest in these methods because of their simplicity, ease of parallelization, and potential for higher accuracy on certain classes of problems ( 29 ) . In this paper, we consider the one-sided Jacobi algorithm for computing the SVD of many relatively small problems (i.e., a batch SVD) using GPUs. The developed batch SVD solver brings a number of novel algorithmic and design techniques that combine performance with numerical robustness, and is publicly available through the open-source MAGMA library ( 12 ; 1 ) . Here is a list of our contributions. (1) We present a GPU-accelerated batch SVD solver that outperforms the state of the art. The solver supports matrices of any shape and size, as long as the batch fits in the GPU memory. Unlike other

Read the complete text