Schost, Eric ;
Bostan, Alin ;
Jeannerod, ClaudePierre
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 Cauchylikeness.
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 BitmeadAnderson, Morf, Kaltofen, GohbergOlshevsky,
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 Vandermondelike matrices, this cost can be
reduced to $O(alpha^(omega1) n)$, where $omega$ is an exponent for
linear algebra. We present consequences for HermitePad'e approximation
and bivariate interpolation.
BibTeX  Entry
@InProceedings{schost_et_al:DSP:2006:778,
author = {Eric Schost and Alin Bostan and ClaudePierre 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 = {18624405},
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, HermitePade, bivariate interpolation}
}
Keywords: 

Structured matrices, matrix multiplication, HermitePade, bivariate interpolation 
Seminar: 

06271  Challenges in Symbolic Computation Software

Issue date: 

2006 
Date of publication: 

25.10.2006 