DBDSVDMR3: An MRRR-Based Bidiagonal SVD Solver Built from DSTEGR
Abstract
The optimal algorithm for the symmetric tridiagonal eigenvalue problem is Multiple Relatively Robust Representations (MRRR or MR3), which is capable of computing k eigenvalue/eigenvector pairs in only O(kn) floating-point operations. While MRRR is nearly 30 years old, it has never successfully been adapted to the bidiagonal SVD. This is not for lack of trying; two previous attempts produced implementations that were considered for LAPACK but eventually abandoned, a result of the fact that neither was reliable enough when run on test problems. The question therefore remained: is there a problem with the theory of MRRR for the bidiagonal SVD or were there simply bugs in the previous implementations that went undetected? This paper resolves this question by presenting DBDSVDMR3 -- a new implementation of the MRRR-based algorithm for the bidiagonal SVD originally proposed by Willems and Lang [ETNA 2012], which, for the first time, performs well on a variety of test problems while achieving significant speedups over both LAPACK's bisection-based solver and, in certain cases, divide-and-conquer for the bidiagonal SVD (thereby indicating that the theory is sound). DBDSVDMR3 will be available in the next release of LAPACK. In this paper, we discuss the design of our implementation, which was obtained with the help of Claude Code, and exhibit its performance on a diverse set of test problems.
Related
- Piñeiro mixed orthogonal polynomials and bidiagonal factorization
- Positive Bidiagonal Factorizations and Mixed-Type Chebyshev Multiple Orthogonal Polynomials
- Positive Bidiagonal Factorizations: Combinatorial Structure, Spectral Theory, and Matrix Continued Fractions
- Positive Bidiagonal Factorizations for Banded Markov Processes
- LOCO-AdaMP: Built-in LOCO Inference for Adaptive Minipatch Ensembles with Enhanced Prediction
BibTeX
@misc{demmel2026dbdsvdmr3,
title = {{DBDSVDMR3: An MRRR-Based Bidiagonal SVD Solver Built from DSTEGR}},
author = {James Demmel and Inderjit Dhillon and Sai Surya Duvvuri and Julien Langou and Osni Marques and Ryan Schneider},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.30227},
eprint = {2610.30227},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.30227},
note = {CC BY-NC-ND 4.0},
}
RIS
TY - UNPB
TI - DBDSVDMR3: An MRRR-Based Bidiagonal SVD Solver Built from DSTEGR
AU - James Demmel
AU - Inderjit Dhillon
AU - Sai Surya Duvvuri
AU - Julien Langou
AU - Osni Marques
AU - Ryan Schneider
PY - 2026
DA - 2026/10/21
PB - arXiv
DO - 10.48550/arxiv.2610.30227
UR - https://arxiv.org/abs/2610.30227
AB - The optimal algorithm for the symmetric tridiagonal eigenvalue problem is Multiple Relatively Robust Representations (MRRR or MR^3), which is capable of computing k eigenvalue/eigenvector pairs in only O(kn) floating-point operations. While MRRR is nearly 30 years old, it has never successfully been adapted to the bidiagonal SVD. This is not for lack of trying; two previous attempts produced implementations that were considered for LAPACK but eventually abandoned, a result of the fact that neither was reliable enough when run on test problems. The question therefore remained: is there a problem with the theory of MRRR for the bidiagonal SVD or were there simply bugs in the previous implementations that went undetected? This paper resolves this question by presenting DBDSVDMR3 -- a new implementation of the MRRR-based algorithm for the bidiagonal SVD originally proposed by Willems and Lang [ETNA 2012], which, for the first time, performs well on a variety of test problems while achieving significant speedups over both LAPACK's bisection-based solver and, in certain cases, divide-and-conquer for the bidiagonal SVD (thereby indicating that the theory is sound). DBDSVDMR3 will be available in the next release of LAPACK. In this paper, we discuss the design of our implementation, which was obtained with the help of Claude Code, and exhibit its performance on a diverse set of test problems.
ER -