Compression of unitary rank-structured matrices to CMV-like shape with an application to polynomial rootfinding. (English) Zbl 1304.65131
Summary: This paper is concerned with the reduction of a unitary matrix \(U\) to CMV-like shape. A Lanczos-type algorithm is presented which carries out the reduction by computing the block tridiagonal form of the Hermitian part of \(U\), i.e., of the matrix \(U + U^H\). By elaborating on the Lanczos approach we also propose an alternative algorithm using elementary matrices which is numerically stable. If \(U\) is rank-structured then the same property holds for its Hermitian part and, therefore, the block tridiagonalization process can be performed using the rank-structured matrix technology with reduced complexity. Our interest in the CMV-like reduction is motivated by the unitary and almost unitary eigenvalue problem. In this respect, finally, we discuss the application of the CMV-like reduction for the design of fast companion eigensolvers based on the customary QR iteration.
MSC:
| 65F15 | Numerical computation of eigenvalues and eigenvectors of matrices |
| 65H04 | Numerical computation of roots of polynomial equations |
Keywords:
CMV matrices; unitary matrices; rank-structured matrices; block tridiagonal reduction; QR iteration; block Lanczos algorithm; algorithm; eigenvalue problemReferences:
| [1] | Killip, R.; Nenciu, I., CMV: the unitary analogue of Jacobi matrices, Comm. Pure Appl. Math., 60, 8, 1148-1188 (2007) · Zbl 1128.15012 |
| [2] | Cantero, M. J.; Moral, L.; Velázquez, L., Five-diagonal matrices and zeros of orthogonal polynomials on the unit circle, Linear Algebra Appl., 362, 29-56 (2003) · Zbl 1022.42013 |
| [3] | 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 |
| [4] | Vandebril, R.; Watkins, D. S., An extension of the QZ algorithm beyond the Hessenberg-upper triangular pencil, Electron. Trans. Numer. Anal., 40, 17-35 (2013) · Zbl 1288.65053 |
| [5] | Ammar, G. S.; Gragg, W. B.; He, C., An efficient QR algorithm for a Hessenberg submatrix of a unitary matrix, (New Directions and Applications in Control Theory. New Directions and Applications in Control Theory, Lecture Notes in Control and Inform. Sci., vol. 321 (2005), Springer: Springer Berlin), 1-14 · Zbl 1203.65074 |
| [6] | Wang, T. L.; Gragg, W. B., Convergence of the shifted \(Q R\) algorithm for unitary Hessenberg matrices, Math. Comp., 71, 240, 1473-1496 (2002) · Zbl 1003.65031 |
| [7] | Wang, T. L.; Gragg, W. B., Convergence of the unitary QR algorithm with a unimodular Wilkinson shift, Math. Comp., 72, 241, 375-385 (2003) · Zbl 1014.65027 |
| [8] | Bini, D. A.; Eidelman, Y.; Gemignani, L.; Gohberg, I., Fast QR eigenvalue algorithms for Hessenberg matrices which are rank-one perturbations of unitary matrices, SIAM J. Matrix Anal. Appl., 29, 2, 566-585 (2007) · Zbl 1147.65031 |
| [9] | Bini, D. A.; Eidelman, Y.; Gemignani, L.; Gohberg, I., The unitary completion and QR iterations for a class of structured matrices, Math. Comp., 77, 261, 353-378 (2008) · Zbl 1141.65025 |
| [10] | Delvaux, S.; Van Barel, M., Eigenvalue computation for unitary rank structured matrices, J. Comput. Appl. Math., 213, 1, 268-287 (2008) · Zbl 1132.65026 |
| [11] | Eidelman, Y.; Gohberg, I.; Gemignani, L., On the fast reduction of a quasiseparable matrix to Hessenberg and tridiagonal forms, Linear Algebra Appl., 420, 1, 86-101 (2007) · Zbl 1113.65038 |
| [12] | Fiedler, M.; Markham, T. L., Completing a matrix when certain entries of its inverse are specified, Linear Algebra Appl., 74, 225-237 (1986) · Zbl 0592.15002 |
| [13] | Golub, G. H.; Van Loan, C. F., (Matrix Computations. Matrix Computations, Johns Hopkins Studies in the Mathematical Sciences (1996), Johns Hopkins University Press: Johns Hopkins University Press Baltimore, MD) · Zbl 0865.65009 |
| [14] | Tisseur, F., Backward stability of the QR algorithm. Technical Report 239 (1996), UMR 5585 Lyon Saint-Etienne |
| [15] | Delvaux, S.; Van Barel, M., Rank structures preserved by the \(Q R\)-algorithm: the singular case, J. Comput. Appl. Math., 189, 1-2, 157-178 (2006) · Zbl 1090.65044 |
| [16] | Eidelman, Y.; Gohberg, I., A modification of the Dewilde-van der Veen method for inversion of finite structured matrices, Linear Algebra Appl., 343-344, 419-450 (2002), Special issue on structured and infinite systems of linear equations · Zbl 1010.65013 |
| [17] | Eidelman, Y.; Gohberg, I., Out-of-band quasiseparable matrices, Linear Algebra Appl., 429, 1, 266-289 (2008) · Zbl 1144.65018 |
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.
