Twisted factorizations and qd-type transformations for the MR\(^{3}\) algorithm -- new representations and analysis
type: Item
instance of: scholarly article
zbMATH Open document ID: 1267.65044
DOI: 10.1137/110834044
author: Bruno Lang
author: Paul R. Willems
published in: SIAM Journal on Matrix Analysis and Applications
publication date: 2012-09-12T00:00:00Z
Mathematics Subject Classification ID: 65F15
Mathematics Subject Classification ID: 65G50
Mathematics Subject Classification ID: 65F50
Mathematics Subject Classification ID: 15A23
zbMATH DE Number: 6081312
zbMATH Keywords: bidiagonal factorizations
zbMATH Keywords: twisted factorizations
zbMATH Keywords: partial eigenvalues
zbMATH Keywords: symmetric tridiagonal matrices
zbMATH Keywords: multiple relatively robust representations algorithm
zbMATH Keywords: error bounds
zbMATH Keywords: eigenvectors
Wikidata QID: Q114074351
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.1137/110834044
OpenAlex ID: W1984456322
title: Twisted factorizations and qd-type transformations for the MR\(^{3}\) algorithm -- new representations and analysis
review text: 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…
reviewed by: Ştefan M. Şoltuz
description: scientific article; zbMATH DE number 6081312