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

DOI10.1137/19M1280363zbMATH Open1458.65036arXiv1901.08411OpenAlexW3040511941MaRDI QIDQ5146607FDOQ5146607

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)

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.

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

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

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)

Cites Work

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

Cited In (5)

• A unification of unitary similarity transforms to compressed representations
• Orthogonal iterations on companion-like pencils
• 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 Hessenberg Reduction Algorithm for Rank Structured Matrices

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)