Twisted Factorizations and qd-Type Transformations for the $\mbox{MR}^{3}$ Algorithm---New Representations and Analysis
Paul R. Willems, Bruno Lang · SIAM Journal on Matrix Analysis and Applications · 2012
Bidiagonal and twisted factorizations play a prominent role in the $\mbox{MR}^{3}$ algorithm for computing partial eigensystems of symmetric tridiagonal matrices. Bidiagonal factorizations of shifted symmetric tridiagonals ${\mathsf T} - \tau {\mathsf I}$ also underlie, at least implicitly, the evaluation of the Sturm count for eigenvalue computations. In this paper we propose new representations ($e$-rep, $Z$-rep) for bidiagonal and twisted factorizations relying on other quantities than the usually employed nontrivial entries of the bidiagonal factors (${\mathsf N}$-rep). We show that the qd algorithms used for shifting the factorizations, e.g. ${\mathsf L}{\mathsf D}{\mathsf L}^\ast - \tau {\mathsf I} {=\vcentcolon} {\mathsf L}^+{\mathsf D}^+({\mathsf L}^+)^\ast$, and for converting between them, can be formulated to work with these representations in a mixed stable way. In fact, the $Z$-representation achieves lower bounds for the necessary relative perturbations of the inputs and outputs than the traditional ${\mathsf N}$-rep does. To obtain sharp bounds for accumulating perturbations we propose a new notation that extends Higham's [N. J. Higham, Accuracy and Stability of Numerical Algorithms, 2nd ed., SIAM, Philadelphia, PA, 2002] by including second-order terms to provide sharper first-order bounds.