The QR iteration method for Hermitian quasiseparable matrices of an arbitrary order

DOI10.1016/J.LAA.2005.02.037MaRDI QIDQ2484401zbMATH OpenOpenAlexFDO

Authors Y. Eidelman, I. Gohberg, V. Olshevsky

Publication date 1 August 2005

Published in Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.laa.2005.02.037

zbMATH Keywords

Dewilde-van der Veen methodeigenvalue problemHermitian separable matricesnumerical experimentsQR iterationquasi-separable matricessemiseparable matrices

Mathematics Subject Classification ID

Numerical computation of eigenvalues and eigenvectors of matrices (65F15) Complexity and performance of numerical algorithms (65Y20)

Review text

Based on earlier works of the first two authors on special classes of structured matrices the eigenvalue problem for Hermitian quasiseparable matrices is treated. It is well known that the \(QR\) iteration can be implemented very efficiently if it is applied to reduced matrices, e.g. to Hermitian tridiagonal matrices after reduction of Hermitian matrices. The authors show that the efficiency of the \(QR\) iteration can be carried over to Hermitian quasiseparable matrices. Quasiseparable matrices can be represented by generators which are computed applying a modifiction of the Dewilde-van der Veen method [cf. \textit{Y. Eidelman} and \textit{I. Gohberg}, Linear Algebra Appl. 343--344, 419--450 (2002; Zbl 1010.65013)]. The Hermitian quasiseparable structure is inherited under \(QR\) iteration. Proofs and complexity analysis are given. The last section contains numerical experiments and a description of the shift strategy and of the estimation of the accuracy. The numerical tests show that the total number of iterations to compute the eigenvalues of an \((n,n)\) Hermitian quasiseparable matrix is about \(3n\).

Recommendations

• Separable type representations of matrices and fast algorithms. Volume 2. Eigenvalue method
• Efficient eigenvalue computation for quasiseparable Hermitian matrices under low rank perturbations
• Divide and conquer method for eigenstructure of quasiseparable matrices using zeroes of rational matrix functions
• The restarted QR-algorithm for eigenvalue computation of structured matrices
• Numerical solution of the eigenvalue problem for efficiently structured Hermitian matrices
• Eigenvalue computation for unitary rank structured matrices
• A multiple shift \(QR\)-step for structured rank matrices
• An implicit QR algorithm for symmetric semiseparable matrices
• The bisection eigenvalue method for unitary Hessenberg matrices via their quasiseparable structure
• AQZ-method based on semiseparable matrices

Cites work

• A divide-and-conquer algorithm for the eigendecomposition of symmetric block-diagonal plus semiseparable matrices
• A modification of the Dewilde-van der Veen method for inversion of finite structured matrices
• A note on the representation and definition of semiseparable matrices
• An implicit QR algorithm for symmetric semiseparable matrices
• Divide and conquer algorithms for computing the eigendecomposition of symmetric diagonal-plus-semiseparable matrices
• Fast and stable eigendecomposition of symmetric banded plus semi-separable matrices
• Fast and stable reduction of diagonal plus semi-separable matrices to tridiagonal and bidiagonal form
• Fast inversion algorithms for diagonal plus semiseparable matrices
• scientific article; zbMATH DE number 1183880 (Why is no real title available?)
• scientific article; zbMATH DE number 108341 (Why is no real title available?)
• scientific article; zbMATH DE number 1974608 (Why is no real title available?)
• scientific article; zbMATH DE number 1569015 (Why is no real title available?)
• scientific article; zbMATH DE number 3026637 (Why is no real title available?)
• Linear complexity inversion algorithms for a class of structured matrices
• On a new class of structured matrices
• On the shifted QR iteration applied to companion matrices
• Rational Krylov matrices and QR steps on Hermitian diagonal‐plus‐semiseparable matrices

Cited in

(33)

• A multiple shift \(QR\)-step for structured rank matrices
• The restarted QR-algorithm for eigenvalue computation of structured matrices
• Separable type representations of matrices and fast algorithms. Volume 2. Eigenvalue method
• Computations with quasiseparable polynomials and matrices
• Time and space efficient generators for quasiseparable matrices
• A Levinson-like algorithm for symmetric strongly nonsingular higher order semiseparable plus band matrices
• Fast QR factorization of Cauchy-like matrices
• Neville elimination for rank-structured matrices
• Efficient eigenvalue computation for quasiseparable Hermitian matrices under low rank perturbations
• Eigenstructure of order-one-quasiseparable matrices. Three-term and two-term recurrence relations
• On the convergence properties of the orthogonal similarity transformations to tridiagonal and semiseparable (plus diagonal) form
• On the \(QR\) iterations of real matrices
• Superfast divide-and-conquer method and perturbation analysis for structured eigenvalue solutions
• Quasiseparable Hessenberg reduction of real diagonal plus low rank matrices and applications
• On the description and stability of orthogonal transformations of rank structured matrices
• Fast algorithms for hierarchically semiseparable matrices
• \textit{qd}-type methods for quasiseparable matrices
• A numerical method for determining monotonicity and convergence rate in iterative learning control
• Rational Krylov matrices and QR steps on Hermitian diagonal‐plus‐semiseparable matrices
• A fast contour-integral eigensolver for non-Hermitian matrices
• SuperDC: superfast divide-and-conquer eigenvalue decomposition with improved stability for rank-structured matrices
• Singular matrices whose Moore-Penrose inverse is tridiagonal
• Representation of quasiseparable matrices using excluded sums and equivalent charges
• Structured condition numbers for Sylvester matrix equation with parameterized quasiseparable matrices
• Tridiagonal M-matrices with tridiagonal Moore-Penrose inverse
• Structured eigenvalue condition numbers for parameterized quasiseparable matrices
• A fast implicit QR eigenvalue algorithm for companion matrices
• On the fast reduction of a quasiseparable matrix to Hessenberg and tridiagonal forms
• The fast bisection eigenvalue method for Hermitian order one quasiseparable matrices and computations of norms
• AQZ-method based on semiseparable matrices
• Rational QR-iteration without inversion
• A new iteration for computing the eigenvalues of semiseparable (plus diagonal) matrices
• Implicit double shift \(QR\)-algorithm for companion matrices

This page was built for publication: The QR iteration method for Hermitian quasiseparable matrices of an arbitrary order

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