Volume 39, pp. 1-21, 2012.

The MR3-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, MR3, for this task by casting the singular value problem in terms of a suitable tridiagonal symmetric eigenproblem (via the Golub–Kahan matrix). Just running MR3 “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 MR3 as a black box solver on the Golub–Kahan matrix. We show that, in contrast to standing opinion, MR3 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 MR3 algorithm