Computing the Characteristic Polynomial of Generic Toeplitz-like and Hankel-like Matrices
share
New algorithms are presented for computing annihilating polynomials of Toeplitz, Hankel, and more generally Toeplitz+ Hankel-like matrices over a field. Our approach follows works on Coppersmith's block Wiedemann method with structured projections, which have been recently successfully applied for computing the bivariate resultant. A first baby-step/giant step approach – directly derived using known techniques on structured matrices – gives a randomized Monte Carlo algorithm for the minimal polynomial of an n× n Toeplitz or Hankel-like matrix of displacement rank α using Õ(n^ω - c(ω)α^c(ω)) arithmetic operations, where ω is the exponent of matrix multiplication and c(2.373)≈ 0.523 for the best known value of ω. For generic Toeplitz+Hankel-like matrices a second algorithm computes the characteristic polynomial in Õ(n^2-1/ω) operations when the displacement rank is considered constant. Previous algorithms required O(n^2) operations while the exponents presented here are respectively less than 1.86 and 1.58 with the best known estimate for ω.
READ FULL TEXT