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