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:DSP:2006:778,
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 = {http://drops.dagstuhl.de/opus/volltexte/2006/778},
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
