     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 .

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) . 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 . For the other classes of structured matrices we refer the reader to  and .

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 . 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