Using fast matrix multiplication to solve structured linear systems

Abstract

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. Then, for the families of matrices given above,
the results of Bitmead-Anderson, Morf, Kaltofen, Gohberg-Olshevsky,
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- 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-Pad'e approximation
and bivariate interpolation.