Séminaire du 20 novembre 06, Éric Schost, London, Ontario, Canada.
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)
Virginie Collette
Last modified: Mon May 23 18:32:54 CEST 2005