Using fast matrix multiplication in structured linear algebra.

Structured linear algebra techniques are a versatile set of tools; they enable one to deal at once with various types of matrices, with features such as Toeplitz-, Hankel-, Vandermonde- or Cauchy-likeness. Following Kailath, Kung and Morf (1979), the usual way of measuring to what extent a matrix possesses one such structure is through its displacement rank, that is, the rank of its image through a suitable displacement operator. For the families of matrices given above, the results of Bitmeand-Anderson, Morf, Kaltofen, Gohberg-Olshevksy, Pan (among others) provide algorithm of complexity $O(\alpha^2 n)$, up to logarithmic factors, where $n$ is the matrix size and $\alpha$ its displacement rank. We show that for Toeplitz- and Vandermonde-like matrices, this cost can be reduced to $O(\alpha^{\omega-1} n)$, where $\omega$ is an exponent for linear algebra. We present consequences for Hermite-Pade approximation and bivariate interpolation. (Joint work with Alin Bostan and Claude-Pierre Jeannerod)