Volume 39, pp. 1-21, 2012.

The ${\text{MR}}^3$-GK algorithm for the bidiagonal SVD

Paul R. Willems and Bruno Lang

Abstract

Determining the singular value decomposition of a bidiagonal matrix is a frequent subtask in numerical computations. We shed new light on a long-known way to utilize the algorithm of multiple relatively robust representations, ${\text{MR}}^3$, for this task by casting the singular value problem in terms of a suitable tridiagonal symmetric eigenproblem (via the Golub–Kahan matrix). Just running ${\text{MR}}^3$ “as is” on the tridiagonal problem does not work, as has been observed before (e.g., by B. Großer and B. Lang [Linear Algebra Appl., 358 (2003), pp. 45–70]). In this paper we give more detailed explanations for the problems with running ${\text{MR}}^3$ as a black box solver on the Golub–Kahan matrix. We show that, in contrast to standing opinion, ${\text{MR}}^3$ can be run safely on the Golub–Kahan matrix, with just a minor modification. A proof including error bounds is given for this claim.

Full Text (PDF) [307 KB], BibTeX

Key words

bidiagonal matrix, singular value decomposition, MRRR algorithm, theory and implementation, Golub–Kahan matrix

AMS subject classifications

65F30, 65F15, 65G50, 15A18

Links to the cited ETNA articles

[36]	Vol. 38 (2011), pp. 363-400 Paul R. Willems and Bruno Lang: Block factorizations and qd-type transformations for the ${\text{MR}}^3$ algorithm