Solving structured linear systems with large displacement rank

International audienceLinear systems with structures such as Toeplitz, Vandermonde 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 such 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 present consequences for Hermite--Pad\'e approximation and bivariate interpolation