Fast Hessenberg reduction of some rank structured matrices

DOI10.1137/16M1107851MaRDI QIDQ5270421zbMATH OpenOpenAlexFDO

Authors L. Gemignani, Leonardo Robol

Publication date 23 June 2017

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

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

zbMATH Keywords

algorithmblock companion matricesblock Lanczos-type procedureblock tridiagonalizationbulge chasingCMV matrixcomplexityHessenberg reductionquasi-separable matrices

Mathematics Subject Classification ID

Abstract: We develop two fast algorithms for Hessenberg reduction of a structured matrix $A=D+U{V}^H$ where $D$ is a real or unitary $nimesn$ diagonal matrix and $U,Vinmathbb{C}^{nimesk}$. The proposed algorithm for the real case exploits a two--stage approach by first reducing the matrix to a generalized Hessenberg form and then completing the reduction by annihilation of the unwanted sub-diagonals. It is shown that the novel method requires $O(n^{2}k)$ arithmetic operations and it is significantly faster than other reduction algorithms for rank structured matrices. The method is then extended to the unitary plus low rank case by using a block analogue of the CMV form of unitary matrices. It is shown that a block Lanczos-type procedure for the block tridiagonalization of $Re(D)$ induces a structured reduction on $A$ in a block staircase CMV--type shape. Then, we present a numerically stable method for performing this reduction using unitary transformations and we show how to generalize the sub-diagonal elimination to this shape, while still being able to provide a condensed representation for the reduced matrix. In this way the complexity still remains linear in $k$ and, moreover, the resulting algorithm can be adapted to deal efficiently with block companion matrices.

Recommendations

• A Hessenberg Reduction Algorithm for Rank Structured Matrices
• Efficient reduction of compressed unitary plus low rank matrices to Hessenberg form
• Quasiseparable Hessenberg reduction of real diagonal plus low rank matrices and applications
• On the fast reduction of a quasiseparable matrix to Hessenberg and tridiagonal forms
• Fast QR Eigenvalue Algorithms for Hessenberg Matrices Which Are Rank‐One Perturbations of Unitary Matrices

Cites work

• O( n^2 ) Reduction Algorithms for the Construction of a Band Matrix from Spectral Data
• A CMV-Based Eigensolver for Companion Matrices
• A framework for symmetric band reduction
• A Hessenberg Reduction Algorithm for Rank Structured Matrices
• A note on matrix inversion
• Blocked algorithms for the reduction to Hessenberg-triangular form revisited
• CMV matrices: Five years after
• CMV: The unitary analogue of Jacobi matrices
• Completing a matrix when certain entries of its inverse are specified
• Compression of unitary rank-structured matrices to CMV-like shape with an application to polynomial rootfinding
• Conservative discrete time-invariant systems and block operator CMV matrices
• Efficient eigenvalue computation for quasiseparable Hermitian matrices under low rank perturbations
• Five-diagonal matrices and zeros of orthogonal polynomials on the unit circle
• scientific article; zbMATH DE number 5527834 (Why is no real title available?)
• scientific article; zbMATH DE number 3756646 (Why is no real title available?)
• Linearization of matrix polynomials expressed in polynomial bases
• Matrix computations and semiseparable matrices. Vol. 1: Linear systems.
• On a class of matrix pencils and -ifications equivalent to a given matrix polynomial
• On the fast reduction of a quasiseparable matrix to Hessenberg and tridiagonal forms
• On the Spectral Decomposition of Hermitian Matrices Modified by Low Rank Perturbations with Applications
• Orthonormal polynomial vectors and least squares approximation for a discrete inner product
• Quasiseparable Hessenberg reduction of real diagonal plus low rank matrices and applications
• Schur parameter pencils for the solution of the unitary eigenproblem
• Separable type representations of matrices and fast algorithms. Volume 2. Eigenvalue method

Cited in

(13)

• Sampling the eigenvalues of random orthogonal and unitary matrices
• CMV block matrices for symmetric matrix measures on the unit circle
• Fast QR iterations for unitary plus low rank matrices
• Data-dependent orthogonal polynomials on generalized circles: a unified approach applied to \(\delta \)-domain identification
• Quasiseparable Hessenberg reduction of real diagonal plus low rank matrices and applications
• A Hessenberg Reduction Algorithm for Rank Structured Matrices
• Compression of unitary rank-structured matrices to CMV-like shape with an application to polynomial rootfinding
• Rank-Structured QR for Chebyshev Rootfinding
• Efficient reduction of compressed unitary plus low rank matrices to Hessenberg form
• Implementing Hager's exchange methods for matrix profile reduction
• A unification of unitary similarity transforms to compressed representations
• Computing eigenvalues of quasi-rational Said-Ball-Vandermonde matrices
• Structured backward errors in linearizations

This page was built for publication: Fast Hessenberg reduction of some rank structured matrices

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