A fast algorithm for index of annihilation computations

DOI10.1016/S0377-0427(99)00103-XMaRDI QIDQ1807796zbMATH OpenFDO

Authors Yanyan Li

Publication date 11 January 2001

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

Full work available at URL https://doi.org/10.1016/S0377-0427(99)00103-X

zbMATH Keywords

fast algorithmindex of annihilationrank revealing QR decompositionsparse Toeplitz matrix

Mathematics Subject Classification ID

Canonical structure (93B10)

Review text

A new, fast algorithm to compute the index of annihilation of the associated pencil of a given matrix is presented. The procedure can be used to compute the elementary divisors of a given square matrix, with real or complex coefficients. The numerical procedure, based on the use of a sparse Toeplitz matrix and exploiting the rank revealing QR decomposition, is faster than existing algorithms based on the SVD approach, and stable. The reliability indices are controlled by quantities that can be computed by the algorithm. The computational complexity of the method is discussed and its performance is tested on a number of examples, considering different types of problems including well-conditioned and ill-conditioned.

Recommendations

• Accelerating an Iterative Process by Explicit Annihilation
• scientific article; zbMATH DE number 647772
• scientific article; zbMATH DE number 7536575
• Faster combinatorial algorithms for determinant and Pfaffian
• Faster Combinatorial Algorithms for Determinant and Pfaffian
• Fast algorithms for direct enclosures and direct dominances
• An algorithmic approach to the Conley index theory
• A fast algorithm for calculating s-invariants
• A Fast Algorithm for Trummer’s Problem
• Efficient algorithms for the scaled indexing problem

Cites work

• An Algorithm for Numerical Computation of the Jordan Normal Form of a Complex Matrix
• An algorithm for numerical determination of the structure of a general matrix
• Error analysis of QR decompositions by Givens transformations
• scientific article; zbMATH DE number 192975 (Why is no real title available?)
• scientific article; zbMATH DE number 1234596 (Why is no real title available?)
• scientific article; zbMATH DE number 3296351 (Why is no real title available?)
• scientific article; zbMATH DE number 961607 (Why is no real title available?)
• Rang revealing QR factorizations
• Some Applications of the Rank Revealing QR Factorization
• The dimension of matrices (matrix pencils) with given Jordan (Kronecker) canonical forms

Cited in

(3)

• On the computation of the rank of block bidiagonal Toeplitz matrices
• The Weierstrass Canonical Form of a Regular Matrix Pencil: Numerical Issues and Computational Techniques
• scientific article; zbMATH DE number 7536575 (Why is no real title available?)

This page was built for publication: A fast algorithm for index of annihilation computations

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