@article{BoJeSc08,
author = {Bostan, Alin and Jeannerod, Claude-Pierre and Schost, \'Eric},
title = {Solving structured linear systems with large displacement rank},
journal = {Theoretical Computer Science},
volume = {407},
number = {1-3},
year = {2008},
pages = {155--181},
doi = {http://dx.doi.org/10.1016/j.tcs.2008.05.014},
publisher = {Elsevier Science Publishers Ltd.},
address = {Essex, UK},
abstract = {Linear systems with structures such as Toeplitz-, Vander\-mon
de- or Cauchy-likeness can be solved in $\tilde O (\alpha^2 n)$
operations, wher e $n$ is the matrix size, $\alpha$ is its displacement
rank, and $\tilde O (\,)$ denotes the omission of logarithmic factors. We
show that for such matrices, th is cost can be reduced to $\tilde O
(\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 $\tilde O (\alpha^{1.38}
n)$. We present consequences for Hermite-Pad\'e approximation an d
bivariate interpolation.},
}