Compression of unitary rank-structured matrices to CMV-like shape with an application to polynomial rootfinding

DOI10.1016/J.CAM.2014.09.023MaRDI QIDQ475676zbMATH OpenOpenAlexFDO

Authors Roberto Bevilacqua, Gianna M. Del Corso, L. Gemignani

Publication date 27 November 2014

Published in Journal of Computational and Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1307.2186

zbMATH Keywords

algorithmeigenvalue problemblock Lanczos algorithmCMV matricesunitary matricesblock tridiagonal reductionQR iterationrank-structured matrices

Mathematics Subject Classification ID

Numerical computation of eigenvalues and eigenvectors of matrices (65F15) Numerical computation of roots of polynomial equations (65H04)

Abstract: 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.

Recommendations

• A CMV-Based Eigensolver for Companion Matrices
• Fast Hessenberg reduction of some rank structured matrices
• Eigenvalue computation for unitary rank structured matrices
• The CMV matrix and the generalized Lanczos process
• Efficient reduction of compressed unitary plus low rank matrices to Hessenberg form

Cites work

• scientific article; zbMATH DE number 961607 (Why is no real title available?)
• A modification of the Dewilde-van der Veen method for inversion of finite structured matrices
• An Efficient QR Algorithm for a Hessenberg Submatrix of a Unitary Matrix
• An extension of the \(QZ\) algorithm beyond the Hessenberg-upper triangular pencil
• CMV: The unitary analogue of Jacobi matrices
• Completing a matrix when certain entries of its inverse are specified
• Convergence of the shifted $QR$ algorithm for unitary Hessenberg matrices
• Convergence of the unitary $QR$ algorithm with a unimodular Wilkinson shift
• Eigenvalue computation for unitary rank structured matrices
• Fast QR Eigenvalue Algorithms for Hessenberg Matrices Which Are Rank‐One Perturbations of Unitary Matrices
• Five-diagonal matrices and zeros of orthogonal polynomials on the unit circle
• On the fast reduction of a quasiseparable matrix to Hessenberg and tridiagonal forms
• Out-of-band quasiseparable matrices
• Rank structures preserved by the QR-algorithm: the singular case
• Schur parameter pencils for the solution of the unitary eigenproblem
• The unitary completion and QR iterations for a class of structured matrices

Cited in

(5)

• Fast Hessenberg reduction of some rank structured matrices
• Editorial: Advanced methods for space-time environmental data
• Factoring block Fiedler companion matrices
• A CMV-Based Eigensolver for Companion Matrices
• Sampling the eigenvalues of random orthogonal and unitary matrices

This page was built for publication: Compression of unitary rank-structured matrices to CMV-like shape with an application to polynomial rootfinding

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q475676)