Stable Matrix-Free Q-less QR via Preconditioning and Randomization
Abstract
This article develops matrix-free Q-less QR algorithms for orthogonalizing tall linear operators. Our main algorithm, CQRRTO, uses randomized preconditioning to make a single Cholesky QR pass numerically safe for any numerically full-rank operator, overcoming the stability issues of Cholesky QR and related methods that operate on the Gram matrix. Compared with deterministic stabilized variants such as Q-less Cholesky QR2 (reorthogonalized Cholesky QR), it remains numerically stable under substantially weaker conditioning assumptions while requiring fewer operator applications. Matrix-free Q-less QR can be useful for improving the numerical robustness of least-squares solves via the normal equations, spectral approximations in a low-dimensional basis, and inversion of operators with low-rank updates via the Woodbury identity. We present a componentwise stability analysis of preconditioned Q-less Cholesky QR that applies to matrix-free operators and is modular with respect to the preconditioner, yielding guarantees for Q-less Cholesky QR, Cholesky QR2, shifted Cholesky QR3, and CQRRTO as special cases. All methods are implemented in the open-source RandLAPACK library.
Related
- A Novel Matrix-Free Approximate Elemental Inverse for Efficient Preconditioning of Discontinuous Galerkin Spectral Elements
- Proper conflict-free degree-choosability of graphs with maximum average degree less than 8/3
- Fast and Stable Arbitrary Precision Approximate Matrix Multiplication
- A MATLAB Tool for the Stable Generation of Matrix Polynomial Evaluation Schemes with Two-Product Savings
- Representation-free Densities of Ratios and Powers of Stable Variables
BibTeX
@misc{balabanov2026stable,
title = {{Stable Matrix-Free Q-less QR via Preconditioning and Randomization}},
author = {Oleg Balabanov and Maksim Melnichenko and Michael W. Mahoney},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.16101},
eprint = {2610.16101},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.16101},
}
RIS
TY - UNPB
TI - Stable Matrix-Free Q-less QR via Preconditioning and Randomization
AU - Oleg Balabanov
AU - Maksim Melnichenko
AU - Michael W. Mahoney
PY - 2026
DA - 2026/10/12
PB - arXiv
DO - 10.48550/arxiv.2610.16101
UR - https://arxiv.org/abs/2610.16101
AB - This article develops matrix-free Q-less QR algorithms for orthogonalizing tall linear operators. Our main algorithm, CQRRTO, uses randomized preconditioning to make a single Cholesky QR pass numerically safe for any numerically full-rank operator, overcoming the stability issues of Cholesky QR and related methods that operate on the Gram matrix. Compared with deterministic stabilized variants such as Q-less Cholesky QR2 (reorthogonalized Cholesky QR), it remains numerically stable under substantially weaker conditioning assumptions while requiring fewer operator applications. Matrix-free Q-less QR can be useful for improving the numerical robustness of least-squares solves via the normal equations, spectral approximations in a low-dimensional basis, and inversion of operators with low-rank updates via the Woodbury identity. We present a componentwise stability analysis of preconditioned Q-less Cholesky QR that applies to matrix-free operators and is modular with respect to the preconditioner, yielding guarantees for Q-less Cholesky QR, Cholesky QR2, shifted Cholesky QR3, and CQRRTO as special cases. All methods are implemented in the open-source RandLAPACK library.
ER -