## Block factorizations and qd-type transformations for the MR3 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]

### Key words

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

### AMS subject classifications

65F15, 65G50, 15A18