** Next:** A Brief Survey of
** Up:** Matrix-Vector and Matrix-Matrix Multiplications
** Previous:** CDS Matrix-Vector Product
** Contents**
** Index**

##

Fast Matrix-Vector Multiplication for Structured Matrices

Dense matrices that depend on parameters arise often in practice.
Examples of these matrices include

Vandermonde:

Toeplitz:

Hankel:
,

Cauchy:
,
and others [257].

These matrices and their inverses can be multiplied
by vectors in time, where
, instead
of or time, depending on the structure.
This is particularly useful for using iterative solvers with
these matrices. The iterative solvers are also useful when solving systems
of the form , where and are both structured but
belong to different structured classes, or if is structured
and is banded or sparse, etc. Iterative methods are also useful for
solving block systems when the blocks are structured
matrices but belong to different structure classes with some
blocks also possibly being sparse. For example, the product

where is diagonal and and are Toeplitz can be formed in
time.
Vandermonde and inverses of Vandermonde matrices can be multiplied
by a vector in time [196,195].
The same is valid for
the Vandermonde-like and inverses of Vandermonde-like
matrices, where ``-like'' matrices are defined as
in § 10.3.4.
Matrix-vector multiplication for Toeplitz and Toeplitz-like
matrices takes
time using the fast Fourier transform (FFT) [198].
The Cauchy matrix-vector product is equivalent
to the evaluation of the function

at different points
and can be done in time by using the
fast multipole method [76,205].
The rest of this section shows
how the matrix-vector multiplication works for
Toeplitz matrices [198].
For the other classes of structured matrices we refer the reader to
[196] and [195].

A circulant matrix is a special Toeplitz matrix of the form

which has the property that
for
.
Circulant matrices are diagonalized by the FFT,
i.e.,

where
and is the Fourier matrix
.
It is a well-known fact that is unitary and a product
can be formed in time [453].
A product can also be formed in time
by the following four steps:

`
(1) ,
`

(2) ,

(3) ,

(4) .

Now, if is a Toeplitz matrix

then the product can be
computed in time by first embedding into a
circulant matrix , since

and

** Next:** A Brief Survey of
** Up:** Matrix-Vector and Matrix-Matrix Multiplications
** Previous:** CDS Matrix-Vector Product
** Contents**
** Index**
Susan Blackford
2000-11-20