Solving structured linear systems with large displacement rank

摘要

Linear systems with structures such as Toeplitz, Vandermonde or Cauchy-likeness can be solved in O{sup}～(α{sup}2n) operations, where n is the matrix size, α is its displacement rank, and Q denotes the omission of logarithmic factors. We show that for such matrices, this cost can be reduced to O{sup}～(α{sup}(ω-1)n), where ω is a feasible exponent for matrix multiplication over the base field. The best known estimate for co is ω < 2.38, resulting in costs of order O{sup}～(α{sup}1.38n). We present consequences for Hermite-Pade approximation and bivariate interpolation.