×

A CS decomposition for orthogonal matrices with application to eigenvalue computation. (English) Zbl 1316.65044

Summary: We show that a Schur form of a real orthogonal matrix can be obtained from a full CS decomposition. Based on this fact a CS decomposition-based orthogonal eigenvalue method is developed. We also describe an algorithm for orthogonal similarity transformation of an orthogonal matrix to a condensed product form, and an algorithm for full CS decomposition. The latter uses mixed shifted and zero-shift iterations for high accuracy. Numerical examples are presented.

MSC:

65F15 Numerical computation of eigenvalues and eigenvectors of matrices
15A23 Factorization of matrices
15B10 Orthogonal matrices

Software:

UDC
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ammar, G. S.; Gragg, W. B.; Reichel, L., On the eigenproblem for orthogonal matrices, (Proceedings of the 25th Conference on Decision and Control (1986), IEEE: IEEE Piscataway), 1963-1966
[2] Ammar, G. S.; Gragg, W. B.; Reichel, L., Determination of Pisarenko frequency estimates as eigenvalues of an orthogonal matrix, (Luk, F. T., Advanced Algorithms and Architectures for Signal Processing II. Advanced Algorithms and Architectures for Signal Processing II, Proc. SPIE Int. Soc. Opt. Eng., vol. 826 (1987), The International Society for Optical Engineering: The International Society for Optical Engineering Bellingham, WA), 143-145
[3] Ammar, G. S.; Reichel, L.; Sorensen, D. C., Algorithm 730: an implementation of a divide and conquer algorithm for the unitary eigenproblem, ACM Trans. Math. Software. ACM Trans. Math. Software, ACM Trans. Math. Software, 20, 161-307 (1994) · Zbl 0894.65017
[4] Bunse-Gerstner, A.; Elsner, L., Schur parameter pencils for the solution of the unitary eigenproblem, Linear Algebra Appl., 154/156, 741-778 (1991) · Zbl 0741.65029
[5] Demmel, J.; Kahan, W., Accurate singular values of bidiagonal matrices, SIAM J. Sci. Statist. Comput., 11, 873-912 (1990) · Zbl 0705.65027
[6] Golub, G. H.; Van Loan, C. F., Matrix Computations (1996), Johns Hopkins University Press: Johns Hopkins University Press Baltimore · Zbl 0865.65009
[7] Gragg, W. B., Positive definite Toeplitz matrices, the Arnoldi process for isometric operators, and Gaussian quadrature on the unit circle, J. Comput. Appl. Math.. (Nikolaev, E. S., Numerical Methods in Linear Algebra (1982), Moscow University Press: Moscow University Press Moscow), 46, 16-32 (1993), this is a slightly edited version of a paper published in Russian · Zbl 0777.65013
[8] Gragg, W. B., The QR algorithm for unitary Hessenberg matrices, J. Comput. Appl. Math., 16, 1-8 (1986) · Zbl 0623.65041
[9] Gragg, W. B., Stabilization of the UHQR-algorithm, (Chen, Z.; Li, Y.; Micchelli, C. A.; Xu, Y., Advances in Computational Mathematics (1999), Marcel Dekker: Marcel Dekker New York), 139-154 · Zbl 0932.65047
[10] Gragg, W. B.; Reichel, L., A divide and conquer method for unitary eigenproblems, (Heath, M. T., Hypercube Multiprocessors 1987 (1987), SIAM: SIAM Philadelphia), 639-647 · Zbl 0708.65039
[11] Gragg, W. B.; Reichel, L., A divide and conquer method for unitary and orthogonal eigenproblems, Numer. Math., 57, 695-718 (1990) · Zbl 0708.65039
[12] Gu, M.; Guzzo, R.; Chi, X.-B.; Cao, X.-Q., A stable divide and conquer algorithm for the unitary eigenproblem, SIAM J. Matrix Anal. Appl., 25, 385-404 (2003) · Zbl 1053.65026
[13] Jones, W. B.; Njåstad, O.; Thron, W. J., Moment theory, orthogonal polynomials, quadrature and continued fractions associated with the unit circle, Bull. Lond. Math. Soc., 21, 113-152 (1989) · Zbl 0637.30035
[14] Reichel, L.; Ammar, G. S., Fast approximation of dominant harmonics by solving an orthogonal eigenvalue problem, (McWhirter, J. G., Mathematics in Signal Processing II (1990), Oxford University Press: Oxford University Press Oxford), 575-591
[15] Stewart, M., An error analysis of a unitary Hessenberg QR algorithm, SIAM J. Matrix Anal. Appl., 28, 40-67 (2006) · Zbl 1119.65024
[16] Sutton, B. D., Computing the complete CS decomposition, Numer. Algorithms, 50, 33-65 (2009) · Zbl 1167.65360
[17] Sutton, B. D., Stable computation of the CS decomposition: simultaneous bidiagonalization, SIAM J. Matrix Anal. Appl., 33, 1-21 (2012) · Zbl 1257.65023
[18] Wang, T.-L.; Gragg, W. B., Convergence of the shifted QR algorithm for unitary Hessenberg matrices, Math. Comp., 71, 1473-1476 (2001) · Zbl 1003.65031
[19] Wang, T.-L.; Gragg, W. B., Convergence of the unitary QR algorithm with a unimodular Wilkinson shift, Math. Comp., 72, 375-385 (2002) · Zbl 1014.65027
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.