Twisted factorizations and qd-type transformations for the MR\(^{3}\) algorithm -- new representations and analysis (Q2910968)

For partial eigensystems of symmetric tridiagonal matrices a major role is given to bidiagonal and twisted factorizations in the multiple relatively robust representations (MRRR=MR\(^{3}\)) algorithm. Bidiagonal factorizations give (by top to bottom or bottom to top methods) the lower bidiagonal factorization \(T=LDL^*\) or the upper bidiagonal factorization \(T=URU^*\); where \(D=\mathrm{diag}(d_{1} ,\dots,d_{n})\) and \(R=\mathrm{diag}(r_{1},\dots,r_{n})\) and \(L\) = unit lower bidiagonal and \(U\) = unit upper bidiagonal. The \(d_{i}\;\)and \(r_{i}\) are called pivots.NEWLINENEWLINETwisted factorization (also called BABE-factorization for born at both ends) generalizes the lower and upper bidiagonal factoring. A twisted factorization of \(T\) is given by \(T=N_{k}G_{k}N_{k}^{\ast}\), where \(\left( N_{k}\right) _{1:k}=L_{1:k}\) is unit lower bidiagonal,\ \ \(\left( N_{k}\right) _{1:k}=U_{1:k}\) is the unit upper bidiagonal and \(G_{k}=\mathrm{diag}\left( d_{1,}\dots,d_{k-1},\gamma_{k},r_{k+1},\dots,r_{n}\right) \) is the diagonal.NEWLINENEWLINETwisted factorizations can be regarded as generalizations of lower and upper bidiagonal factorizations. The \(LDL^*\) and \(URU^*\) decompositions are twisted with \(k=n\), \(\gamma_{n}=d_{n}\) and \(k=1\), \(\gamma_{1}=r_{1}\), respectively. Also, if the top-to-bottom factorization breaks down because pivot \(d_{j}=0\), \(j\leq n\), twisted factorizations with indices \(k\leq j\) will still be possible.NEWLINENEWLINEThe contribution consists in two alternative approaches to represent matrices given by twisted factorizations. The usual method is far from being optimal as the paper shows. The representations are called \(e\)-rep and \(z\)-rep against the usual \(N\)-rep. The \(z\)-rep shows significant better error bounds and the \(e\)-rep has better performance characteristics: faster computations, the error analysis is simpler, the off-diagonal entries staying at the same means, so only stored once. The following strategy is proposed: use the \(z\)-rep for all inner nodes in the tree and switch to \(e\)-rep when eigenvectors are computed. Such a mixed method will perform better from all points of view over \(N\)-rep.