Dense matrices that depend on parameters arise often in practice.
Examples of these matrices include
and others .
These matrices and their inverses can be multiplied
by vectors in time, where
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
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
time using the fast Fourier transform (FFT) .
The Cauchy matrix-vector product is equivalent
to the evaluation of the function
The rest of this section shows how the matrix-vector multiplication works for Toeplitz matrices . For the other classes of structured matrices we refer the reader to  and .
A circulant matrix is a special Toeplitz matrix of the form
Now, if is a Toeplitz matrix