Complexity of multiplication with vectors for structured matrices
I.Gohberg
and
Vadim Olshevsky
Fast algorithms for computing the product by a vector are
presented for a number of classes of matrices, including
Toeplitz-like, Vandermonde-like and Cauchy-like matrices (these
matrices are defined using the concept of displacement of a matrix),
and also for their transposes and
inverses.
The algorithm for Toeplitz-like matrices is based on the representations
of these matrices in terms of factor circulants, obtained in
another paper
[GKO95] by the authors.
The algorithms for Cauchy-like and Vandermonde-like
matrices are based on the
transformation of these matrices
into Toeplitz-like matrices, which allows us to exploit FFT, and to dramatically
reduce the arithmetic complexity.
All the actions which are not dependent upon the
coordinates of the input vector are singled out in a separate
preprocessing stage. The proposed algorithms are based on
new representations of these matrices, involving factor circulants.
Related papers:
Formulas for Toeplitz-like matrices (and for their inverses), involving
factor circulants were obtained in
[GO92].
Transformation technique for different calsses of structured matrices
is further developed in [GKO95].
Key words:
Fast and superfast agorithms,
Preprocessing,
Inversion formulas,
Matrix-vector multiplication,
Solving linear systems,
Displacement structure,
Toeplitz-like matrices, Vandermonde-like matrices, Cauchy-like matrices.
AMS subject classification:
15A06, 15A09, 15A57
Vadim Olshevsky's Home page
Vadim Olshevsky
olshevsk@isl.stanford.edu
Last modified: Fri Sep 15 1995