zbMATH — the first resource for mathematics

QRT: A QR-based tridiagonalization algorithm for nonsymmetric matrices. (English) Zbl 1081.65040
The tridiagonalization of a general square matrix represents the most compact similarity reduction that can be computed directly. Attempting to reduce further (diagonalization or bidiagonalization) implies the retrieval of eigenvalues, which can only be done iteratively in general, unless the order of the matrix is under five. As yet, no stable tridiagonalization algorithm has been found. Only one finite, though unstable and impractical, tridiagonalization algorithm due to A. George, Kh. D. Ikramov, E. V. Matushkina and W.-P. Tang [SIAM J. Matrix Anal. Appl. 16, No. 4, 1107–1126 (1995; Zbl 0837.65035)], is known.
In this paper, the authors describe an algorithm for the triagonalization of nonsymmetric matrices. The algorithm involves two stable Householder transformations per step and is twice as expensive as the symmetric tridiagonalization. The robust \(QR\) step provides a solid foundation to the proposed algorithm. It is also shown how to restrict roundoff errors to at most six entries of the size of the matrix.
Finally, a comparison is made with a previous tridiagonalization algorithm of J. J. Dongarra [ACM Trans. Math. Software, 18 No. 4, 392–400 (1992; Zbl 0892.65024)], and G. A. Geist [SIAM J. Matrix Anal. Appl. 12 No. 2, 362–373 (1991; Zbl 0725.65039)], and it is shows that the algorithm is more robust and reliable.

65F30 Other matrix algorithms (MSC2010)
65F15 Numerical computation of eigenvalues and eigenvectors of matrices
65F25 Orthogonalization in numerical linear algebra
15A21 Canonical forms, reductions, classification
Full Text: DOI