Solving structured linear systems with large displacement rank
Linear systems with structures such as Toeplitz, Vandermonde or Cauchy-likeness can be solved in O-similar to(alpha(2)n) operations, where n is the matrix size, alpha is its displacement rank, and O-similar to denotes the omission of logarithmic factors. We show that for such matrices, this cost can be reduced to O-similar to(alpha(omega-1)n), where omega is a feasible exponent for matrix multiplication over the base field. The best known estimate for omega is omega < 2.38, resulting in costs of order O-similar to(alpha(1.38) n). We present consequences for Hermite-Pade approximation and bivariate interpolation. (C) 2008 Elsevier B.V. All rights reserved.
structured linear algebra dense linear algebra