When quoting this document, please refer to the following
URN: urn:nbn:de:0030-drops-7787
Go to the corresponding Portal

Schost, Eric ; Bostan, Alin ; Jeannerod, Claude-Pierre

Using fast matrix multiplication to solve structured linear systems

06271.SchostEric.Paper.778.pdf (0.2 MB)


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.

BibTeX - Entry

  author =	{Eric Schost and Alin Bostan and Claude-Pierre Jeannerod},
  title =	{Using fast matrix multiplication to solve structured linear systems},
  booktitle =	{Challenges in Symbolic Computation Software},
  year =	{2006},
  editor =	{Wolfram Decker and Mike Dewar and Erich Kaltofen and Stephen Watt },
  number =	{06271},
  series =	{Dagstuhl Seminar Proceedings},
  ISSN =	{1862-4405},
  publisher =	{Internationales Begegnungs- und Forschungszentrum f{\"u}r Informatik (IBFI), Schloss Dagstuhl, Germany},
  address =	{Dagstuhl, Germany},
  URL =		{},
  annote =	{Keywords: Structured matrices, matrix  multiplication, Hermite-Pade, bivariate interpolation}

Keywords: Structured matrices, matrix multiplication, Hermite-Pade, bivariate interpolation
Seminar: 06271 - Challenges in Symbolic Computation Software
Issue Date: 2006
Date of publication: 25.10.2006

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI