QRT: A QR-based tridiagonalization algorithm for nonsymmetric matrices. (English) Zbl 1081.65040

Sidje, Roger B.; Burrage, K.

SIAM J. Matrix Anal. Appl. 26, No. 3, 878-900 (2005).

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.

Reviewer: Sonia Pérez Díaz (Madrid)

MSC:

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

Keywords:

matrix reduction; nonsymmetric tridiagonalization; QR factorization; algorithm; Householder transformations

Software:

Algorithm 710; Eigtool; Expokit; testmatrix