@inproceedings{BoJeSc07,
    author      = {Bostan, Alin and Jeannerod, Claude-Pierre and Schost, \'Eric},
    title       = {Solving {T}oeplitz- and {V}andermonde-like Linear Systems with
                   Large Displacement Rank},
    booktitle   = {ISSAC'07: Proceedings of the 2007 international symposium
                   on Symbolic and algebraic computation},
    year        = {2007},
    editor      = {Brown, C. W.},
    publisher   = {ACM Press},
    pages       = {33--40},
    doi         = {10.1145/1277548.1277554},
    abstract    = {Linear systems with structures such as Toeplitz-, Vander\-monde- or
                   Cauchy-likeness can be solved in $O\tilde{~}(\alpha^2 n)$ operations,
                   where $n$ is the matrix size, $\alpha$ is its displacement rank, and
                  $O\tilde{~}$ denotes the omission of logarithmic factors. We show that
                  for Toeplitz-like and Vandermonde-like matrices, this cost can be
                  reduced to $O\tilde{~}(\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\tilde{~}(\alpha^{1.38} n)$. We also present consequences
                  for Hermite-Pad\'e approximation and bivariate interpolation.},
}