A fast algorithm for index of annihilation computations (Q1807796)

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.