Volume 38, pp. 363-400, 2011.

Block factorizations and qd-type transformations for the $\mbox{MR}^3$ algorithm

Paul R. Willems and Bruno Lang

Abstract

Factorizing symmetric tridiagonal matrices and propagating the factorizations to shifted matrices are central tasks in the $\mbox{MR}^3$ algorithm for computing partial eigensystems. In this paper we propose block bidiagonal factorizations $\mbox{LDL}^*$ with $1 \times 1$ and $2 \times 2$ blocks in $\mbox{D}$ as an alternative to the bidiagonal and twisted factorizations used hitherto. With block factorizations, the element growth can be reduced (or avoided altogether), which is essential for the success of the $\mbox{MR}^3$ algorithm, in particular, if the latter is used to determine the singular value decomposition of bidiagonal matrices. We show that the qd algorithm used for shifting bidiagonal factorizations, e.g., $\mbox{LDL}^* - \tau I =: \mbox{L}^+\mbox{D}^+(\mbox{L}^+)^*$ can be extended to work with blocks in a mixed stable way, including criteria for determining a suitable block structure dynamically.

Full Text (PDF) [480 KB], BibTeX

Key words

symmetric tridiagonal matrix, eigensystem, MRRR algorithm, block bidiagonal factorizations, qd algorithm, theory and implementation

AMS subject classifications

65F15, 65G50, 15A18

ETNA articles which cite this article

Vol. 39 (2012), pp. 1-21 Paul R. Willems and Bruno Lang: The ${\mbox{MR}}^{3}$-GK algorithm for the bidiagonal SVD