Efficient reduction of compressed unitary plus low rank matrices to Hessenberg form

DOI10.1137/19M1280363MaRDI QIDQ5146607zbMATH OpenOpenAlexFDO

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

Publication date 26 January 2021

Published in SIAM Journal on Matrix Analysis and Applications (Search for Journal in Brave)

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

zbMATH Keywords

complexity analysisQR methodrank-structured matricesHessenberg reductionbulge chasing

Mathematics Subject Classification ID

Numerical computation of eigenvalues and eigenvectors of matrices (65F15) Numerical methods for low-rank matrix approximation; matrix compression (65F55)

Abstract: We present fast numerical methods for computing the Hessenberg reduction of a unitary plus low-rank matrix $A=G+U{V}^H$, where $Ginmathbb{C}^{nimesn}$ is a unitary matrix represented in some compressed format using $O(nk)$ parameters and $U$ and $V$ are $nimesk$ matrices with $k<n$. At the core of these methods is a certain structured decomposition, referred to as a LFR decomposition, of $A$ as product of three possibly perturbed unitary $k$ Hessenberg matrices of size $n$. It is shown that in most interesting cases an initial LFR decomposition of $A$ can be computed very cheaply. Then we prove structural properties of LFR decompositions by giving conditions under which the LFR decomposition of $A$ implies its Hessenberg shape. Finally, we describe a bulge chasing scheme for converting the initial LFR decomposition of $A$ into the LFR decomposition of a Hessenberg matrix by means of unitary transformations. The reduction can be performed at the overall computational cost of $O(n^{2}k)$ arithmetic operations using $O(nk)$ storage. The computed LFR decomposition of the Hessenberg reduction of $A$ can be processed by the fast QR algorithm presented in [8] in order to compute the eigenvalues of $A$ within the same costs.

Recommendations

• Fast Hessenberg reduction of some rank structured matrices
• A Hessenberg Reduction Algorithm for Rank Structured Matrices
• Eigenvalue computation for unitary rank structured matrices
• Fast QR Eigenvalue Algorithms for Hessenberg Matrices Which Are Rank‐One Perturbations of Unitary Matrices
• Quasiseparable Hessenberg reduction of real diagonal plus low rank matrices and applications

Cites work

• A CMV-Based Eigensolver for Companion Matrices
• A Hessenberg Reduction Algorithm for Rank Structured Matrices
• CMV matrices: Five years after
• CMV: The unitary analogue of Jacobi matrices
• Chasing bulges or rotations? A metamorphosis of the QR-algorithm
• Completing a matrix when certain entries of its inverse are specified
• Conservative discrete time-invariant systems and block operator CMV matrices
• Core-Chasing Algorithms for the Eigenvalue Problem
• Dynamics of unitary operators
• Fast Hessenberg reduction of some rank structured matrices
• Fast QR iterations for unitary plus low rank matrices
• Fast and backward stable computation of eigenvalues and eigenvectors of matrix polynomials
• Five-diagonal matrices and zeros of orthogonal polynomials on the unit circle
• Linearization of matrix polynomials expressed in polynomial bases
• Matrix computations and semiseparable matrices. Vol. 1: Linear systems.
• Numerical algorithms based on analytic function values at roots of unity
• On a class of matrix pencils and \(\ell\)-ifications equivalent to a given matrix polynomial
• On the Spectral Decomposition of Hermitian Matrices Modified by Low Rank Perturbations with Applications
• On the fast reduction of a quasiseparable matrix to Hessenberg and tridiagonal forms
• Orthogonal matrix polynomials and applications
• Schur parameter pencils for the solution of the unitary eigenproblem
• Separable type representations of matrices and fast algorithms. Volume 2. Eigenvalue method
• Stable polefinding and rational least-squares fitting via eigenvalues

Cited in

(5)

• A Hessenberg Reduction Algorithm for Rank Structured Matrices
• Fast Hessenberg reduction of some rank structured matrices
• Compression of unitary rank-structured matrices to CMV-like shape with an application to polynomial rootfinding
• A unification of unitary similarity transforms to compressed representations
• Orthogonal iterations on companion-like pencils

This page was built for publication: Efficient reduction of compressed unitary plus low rank matrices to Hessenberg form

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