DROPS

Document

Using fast matrix multiplication to solve structured linear systems

Authors: Eric Schost, Alin Bostan, and Claude-Pierre Jeannerod

Published in: Dagstuhl Seminar Proceedings, Volume 6271, Challenges in Symbolic Computation Software (2006)

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.

Cite as

Eric Schost, Alin Bostan, and Claude-Pierre Jeannerod. Using fast matrix multiplication to solve structured linear systems. In Challenges in Symbolic Computation Software. Dagstuhl Seminar Proceedings, Volume 6271, pp. 1-5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{schost_et_al:DagSemProc.06271.16,
  author =	{Schost, Eric and Bostan, Alin and Jeannerod, Claude-Pierre},
  title =	{{Using fast matrix multiplication to solve structured linear systems}},
  booktitle =	{Challenges in Symbolic Computation Software},
  pages =	{1--5},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6271},
  editor =	{Wolfram Decker and Mike Dewar and Erich Kaltofen and Stephen Watt},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06271.16},
  URN =		{urn:nbn:de:0030-drops-7787},
  doi =		{10.4230/DagSemProc.06271.16},
  annote =	{Keywords: Structured matrices, matrix multiplication, Hermite-Pade, bivariate interpolation}
}

Search Results

Documents authored by Schost, Eric

Using fast matrix multiplication to solve structured linear systems

Abstract

Cite as

Thanks for your feedback!

Could not send message