Schost, Eric ;
Bostan, Alin ;
Jeannerod, Claude-Pierre
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.
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 |
|
Seminar: |
|
06271 - Challenges in Symbolic Computation Software
|
|
Issue date: |
|
2006 |
|
Date of publication: |
|
25.10.2006 |
25.10.2006
