Structured linear algebra techniques are a versatile set of tools;#R##N#they enable one to deal at once with various types of matrices, with#R##N#features such as Toeplitz-, Hankel-, Vandermonde- or Cauchy-likeness.#R##N##R##N#Following Kailath, Kung and Morf (1979), the usual way of measuring to#R##N#what extent a matrix possesses one such structure is through its#R##N#displacement rank, that is, the rank of its image through a suitable#R##N#displacement operator. Then, for the families of matrices given above,#R##N#the results of Bitmead-Anderson, Morf, Kaltofen, Gohberg-Olshevsky,#R##N#Pan (among others) provide algorithm of complexity $O(alpha^2 n)$, up#R##N#to logarithmic factors, where $n$ is the matrix size and $alpha$ its#R##N#displacement rank.#R##N##R##N#We show that for Toeplitz- Vandermonde-like matrices, this cost can be#R##N#reduced to $O(alpha^(omega-1) n)$, where $omega$ is an exponent for#R##N#linear algebra. We present consequences for Hermite-Pad'e approximation#R##N#and bivariate interpolation.
['Éric Schost', 'Alin Bostan', 'Claude-Pierre Jeannerod']
Using fast matrix multiplication to solve structured linear systems