@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.}, 
}