A GPU-Accelerated Blocked Adaptive Randomized Range Finder Based on an Implicit Householder QR Decomposition
Abstract
Low-rank methods can reduce the memory and computational requirements of deep neural network training in approaches such as GaLore. Randomized range finders offer an attractive alternative to singular value decompositions, particularly when the required rank is determined adaptively from a prescribed approximation tolerance. We introduce a blocked adaptive randomized range finder based on a Householder QR decomposition and an optimized hybrid CPU--GPU implementation. Numerical experiments show that it preserves orthogonality and approximation accuracy in regimes where block Gram--Schmidt without reorthogonalization becomes unstable. The blocked formulation exposes matrix--matrix operations and enables overlap of CPU panel factorization with GPU updates. On an NVIDIA GH200, the overlapped implementation reduces the runtime for the largest tested matrix from 9.91 s on the CPU to 0.407 s. The method provides a stable and efficient building block for low-rank approximation on heterogeneous systems with applications in computational science and engineering.
Related
- An implicit multiscale solver for steady kinetic equations based on wave-particle decomposition
- GPU-Accelerated Nested Schur-Complement Solvers for Atmospheric Flow Simulations Using Horizontally-Explicit, Vertically-Implicit Schemes and Discontinuous Galerkin Methods
- Accelerated Benders decomposition for bi-objective mixed integer programming
- Are implicit schemes needed in adaptive time stepping for PDEs?
- Adaptive Diagonally Implicit Runge-Kutta Methods Devoid of Order Reduction for Semilinear ODEs
BibTeX
@misc{penke2026gpuaccelerated,
title = {{A GPU-Accelerated Blocked Adaptive Randomized Range Finder Based on an Implicit Householder QR Decomposition}},
author = {Carolin Penke and Andreas Herten},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2608.28941},
eprint = {2608.28941},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.28941},
note = {CC BY-SA 4.0},
}
RIS
TY - UNPB
TI - A GPU-Accelerated Blocked Adaptive Randomized Range Finder Based on an Implicit Householder QR Decomposition
AU - Carolin Penke
AU - Andreas Herten
PY - 2026
DA - 2026/10/29
PB - arXiv
DO - 10.48550/arxiv.2608.28941
UR - https://arxiv.org/abs/2608.28941
AB - Low-rank methods can reduce the memory and computational requirements of deep neural network training in approaches such as GaLore. Randomized range finders offer an attractive alternative to singular value decompositions, particularly when the required rank is determined adaptively from a prescribed approximation tolerance. We introduce a blocked adaptive randomized range finder based on a Householder QR decomposition and an optimized hybrid CPU--GPU implementation. Numerical experiments show that it preserves orthogonality and approximation accuracy in regimes where block Gram--Schmidt without reorthogonalization becomes unstable. The blocked formulation exposes matrix--matrix operations and enables overlap of CPU panel factorization with GPU updates. On an NVIDIA GH200, the overlapped implementation reduces the runtime for the largest tested matrix from 9.91 s on the CPU to 0.407 s. The method provides a stable and efficient building block for low-rank approximation on heterogeneous systems with applications in computational science and engineering.
ER -