Efficient GPU-Centered Singular Value Decomposition Using the Divide-and-Conquer Method

Shifang Liu, Huiyuan Li, Hongjiao Sheng, Haoyuan Gui, Xiaoyu ZhangarXiv 2025 · arXiv · OpenReview

TL;DR

This paper introduces a novel GPU-centered Singular Value Decomposition (SVD) algorithm that significantly accelerates computations by performing all operations on the GPU, eliminating costly CPU-GPU data transfers. The method achieves dramatic speedups, up to 1293x, over existing libraries by optimizing core SVD stages like bidiagonalization and divide-and-conquer diagonalization.

What Problem Does This Paper Address?

Singular Value Decomposition (SVD) is a cornerstone of linear algebra, crucial for tasks ranging from data analysis and machine learning to signal processing. However, traditional SVD algorithms, especially on modern heterogeneous CPU-GPU systems, suffer from performance bottlenecks. These bottlenecks stem from slow "panel factorization" steps and, more critically, frequent and time-consuming data transfers between the CPU and GPU. As GPUs become increasingly powerful, these data transfer overheads become a dominant factor limiting overall performance, even for computationally intensive tasks. This paper aims to tackle these limitations by redesigning the SVD workflow to be "GPU-centered."

Methods

The authors propose a "GPU-centered" SVD algorithm that fundamentally restructures the computation and data layout. Key innovations include:

  • GPU-Centric Bidiagonalization: The traditional two-stage bidiagonalization process is reformulated to execute entirely on the GPU. This includes panel factorization and trailing matrix updates, eliminating CPU-GPU data movement. They introduce a "merged-rank-(2b)" update to improve arithmetic intensity.
  • Optimized QR Factorization and Back-Transformations: For tall-and-skinny (TS) matrices, the QR factorization and subsequent singular vector back-transformations are also optimized for GPU execution, leveraging a modified CWY transform and compute-bound BLAS3 operations.
  • GPU-Based Bidiagonal Divide-and-Conquer (BDC): A novel GPU-based BDC algorithm is developed. This algorithm aims to eliminate matrix-level data transfers and enable asynchronous CPU-GPU execution for the diagonalization phase, which is crucial for SVD. This involves optimizing the "lasd2" (deflation) and "lasd3" (merge) subroutines.

Datasets

The paper does not introduce new datasets. Instead, it uses synthetically generated matrices for evaluation. These matrices are created using MAGMA's magma_generate_matrix routine and include four types:

  • random: Uniformly distributed entries.
  • SVD_logrand(θ): Singular values log-uniformly distributed.
  • SVD_arith(θ): Singular values arithmetically distributed.
  • SVD_geo(θ): Singular values geometrically distributed.

The parameter θ represents the condition number. Both square matrices (m=n) and tall-and-skinny (TS) matrices (m >> n) are used.

Key Insights and Ideas

  • Eliminating CPU-GPU Transfers is Paramount: The most significant takeaway is that for modern GPU architectures, minimizing or eliminating CPU-GPU data transfers is more critical for performance gains than simply offloading computation. The proposed method's success hinges on this principle.
  • "GPU-Centered" is More Than Just Offloading: The paper demonstrates that a successful GPU-centric approach requires a holistic redesign of algorithms and data structures, not just porting existing CPU algorithms to the GPU. This involves re-architecting steps like panel factorization and matrix updates.
  • BDC on GPU is a Game Changer: While bidiagonalization is a major bottleneck, the divide-and-conquer diagonalization (BDC) phase, particularly its deflation and merge steps, also presents significant opportunities for GPU acceleration. The authors' GPU-based BDC implementation shows substantial improvements.
  • BLAS3 is King (and MI210 Shines): The method heavily relies on compute-bound BLAS3 operations. The performance advantage on the AMD MI210 GPU is attributed to its superior BLAS3 capabilities compared to the NVIDIA V100, especially for certain operations.

Key Results

The proposed GPU-centered SVD algorithm achieves remarkable performance improvements:

  • Speedups:
    • Up to 1293.64x over rocSOLVER/cuSOLVER on AMD MI210.
  • Up to 7.47x over rocSOLVER/cuSOLVER on NVIDIA V100.
  • Up to 14.10x over MAGMA on AMD MI210.
  • Up to 12.38x over MAGMA on NVIDIA V100.
  • Accuracy: The method preserves high numerical accuracy, comparable to MAGMA and superior to rocSOLVER.
  • Phase-wise Performance: Profiling shows significant speedups across all SVD phases, with the bidiagonalization (gebrd) and diagonalization (bdcdc) phases showing the most dramatic improvements, especially compared to rocSOLVER where bdcqr is the bottleneck.
  • TS Matrices Benefit Most: The performance gains are particularly pronounced for tall-and-skinny matrices, where the ratio of computation to data transfer is more favorable for the GPU-centric approach.

Limitations and Future Work

  • Leaf Node Size: The performance of the bdsdc (BDC) algorithm is sensitive to the leaf node size (block size for subproblems). While an optimal size of 32 was found in experiments, this might need tuning for different hardware or problem characteristics.
  • Hardware Specifics: While the method shows excellent results on both MI210 and V100, the performance differences highlight the impact of underlying hardware capabilities (e.g., BLAS3 performance).
  • Future Work: The paper implicitly suggests that further optimization of specific kernels and exploring asynchronous execution more deeply could yield even greater gains. The authors also mention that a stable MRRR version for SVD is not yet available, hinting at potential future research directions.

Summary updated

Abstract

Singular Value Decomposition (SVD) is a fundamental matrix factorization technique in linear algebra, widely applied in numerous matrix-related problems. However, traditional SVD approaches are hindered by slow panel factorization and frequent CPU-GPU data transfers in heterogeneous systems, despite advancements in GPU computational capabilities. In this paper, we introduce a GPU-centered SVD algorithm, incorporating a novel GPU-based bidiagonal divide-and-conquer (BDC) method. We reformulate the algorithm and data layout of different steps for SVD computation, performing all panel-level computations and trailing matrix updates entirely on GPU to eliminate CPU-GPU data transfers. Furthermore, we integrate related computations to optimize BLAS utilization, thereby increasing arithmetic intensity and fully leveraging the computational capabilities of GPUs. Additionally, we introduce a newly developed GPU-based BDC algorithm that restructures the workflow to eliminate matrix-level CPU-GPU data transfers and enable asynchronous execution between the CPU and GPU. Experimental results on AMD MI210 and NVIDIA V100 GPUs demonstrate that our proposed method achieves speedups of up to 1293.64x/7.47x and 14.10x/12.38x compared to rocSOLVER/cuSOLVER and MAGMA, respectively.
BibTeX
@misc{liu2025efficient,
  author = {Shifang Liu and Huiyuan Li and Hongjiao Sheng and Haoyuan Gui and Xiaoyu Zhang},
  title = {{Efficient GPU-Centered Singular Value Decomposition Using the Divide-and-Conquer Method}},
  year = {2025},
  eprint = {2508.11467},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2508.11467},
}
Figure