Block factorizations and qd-type transformations for the \(\mathrm{MR}^3\) algorithm. (English) Zbl 1321.65058
Summary: Factorizing symmetric tridiagonal matrices and propagating the factorizations to shifted matrices are central tasks in the MR\(^3\) algorithm for computing partial eigensystems. In this paper we propose block bidiagonal factorizations \(LDL^*\) with \(1\times 1\) and \(2 \times 2\) blocks in \(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 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., \(LDL^*-\tau I =: L^+ D^+ (L^+)^*\) can be extended to work with blocks in a mixed stable way, including criteria for determining a suitable block structure dynamically.
MSC:
65F15 | Numerical computation of eigenvalues and eigenvectors of matrices |
65G50 | Roundoff error |
15A18 | Eigenvalues, singular values, and eigenvectors |
15A23 | Factorization of matrices |