License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/DagSemProc.06271.16
URN: urn:nbn:de:0030-drops-7787
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2006/778/
Go to the corresponding Portal

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

Using fast matrix multiplication to solve structured linear systems

pdf-format:
06271.SchostEric.Paper.778.pdf (0.2 MB)

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.

BibTeX - Entry

@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/opus/volltexte/2006/778},
  URN =		{urn:nbn:de:0030-drops-7787},
  doi =		{10.4230/DagSemProc.06271.16},
  annote =	{Keywords: Structured matrices, matrix multiplication, Hermite-Pade, bivariate interpolation}
}

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

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