Fast Matrix-Vector Multiplication for Structured Matrices

Dense matrices that depend on $O(n)$ parameters arise often in practice. Examples of these matrices include

Vandermonde:

$$V = \bmat{cccc} 1 & 1 & \ldots & 1 \\ x_1 & x_2 & \ldots... ...ddots & \\ x_1^{n-1} & x_2^{n-1} & \ldots & x_n^{n-1} \emat,$$

Toeplitz:

$$T = \bmat{ccccc} t_0 & t_{-1} & \ldots &t_{2-n}& t_{1-n} \... ... & t_{-1} \\ t_{n-1 } & t_{n-2 } & \ldots & t_1 & t_0 \emat,$$

Hankel: $H = (H_{ij})=(c_{i+j})$,

Cauchy: $C = (C_{ij})=(\frac{1}{x_i-y_j})$, and others [257].

These matrices and their inverses can be multiplied by vectors in $O(n\log^k n)$ time, where $0 \leq k \leq 2$, instead of $O(n^2)$ or $O(n^3)$ 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 $(A+B)x=b$, where $A$ and $B$ are both structured but belong to different structured classes, or if $A$ is structured and $B$ 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

$$\bmat{cc} A & B \\ C & 0 \emat \bmat{c} x \\ y \emat = \bmat{c} Ax+By \\ Cx \emat,$$

where $A$ is diagonal and $B$ and $C$ are Toeplitz can be formed in $O(n\log n)$ time.

Vandermonde and inverses of Vandermonde matrices can be multiplied by a vector in $O(n\log^2 n)$ 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 $O(n\log n)$ time using the fast Fourier transform (FFT) [198]. The Cauchy matrix-vector product $Cz$ is equivalent to the evaluation of the function

$$\Phi(w)=\sum_{i=1}^n \frac{-z_i}{y_i-w}$$

at $n$ different points $x_1,x_2,\ldots,x_n$ and can be done in $O(n)$ time by using the fast multipole method [76,205].

The rest of this section shows how the $O(n\log n)$ 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

$$C_n = \bmat{ccccc} a_0 & a_{-1} & \ldots &a_{2-n}& a_{1-n}... ...& a_{-1} \\ a_{n-1 } & a_{n-2 } & \ldots & a_1 & a_0 \emat,$$

which has the property that $a_{-k}=a_{n-k}$ for $1\le k \le n-1$. Circulant matrices are diagonalized by the FFT, i.e.,

$$C_n=F_n^* \cdot \diag(F_n a) \cdot F_n,$$

where $a=[a_0,a_1,\ldots,a_n]$ and $F_n$ is the Fourier matrix $F_n(j,k) = \frac{1}{\sqrt{n}} e^{-(j-1)(k-1)2 \pi \sqrt{-1}/n}$. It is a well-known fact that $F_n$ is unitary and a product $F_n x$ can be formed in $O(n\log n)$ time [453]. A product $y=C_n x$ can also be formed in $O(n\log n)$ time by the following four steps:

		 		 (1) 		 		  $f =F_nx$,  

(2) 		 		 $g =F_na$,  

(3) 		 		 $z^T=[f_1g_1,f_2g_2,\ldots,f_n g_n]$, 

(4) 		 		 $y=F_n^*z$. 

Now, if $T_n$ is a Toeplitz matrix

$$T_n = \bmat{ccccc} t_0 & t_{-1} & \ldots &t_{2-n}& t_{1-n}... ... & t_{-1} \\ t_{n-1 } & t_{n-2 } & \ldots & t_1 & t_0 \emat,$$

then the product $T_nx$ can be computed in $O(n\log n)$ time by first embedding $T_n$ into a $2n\times 2n$ circulant matrix $C_{2n}$, since

$$C_{2n} \cdot \bmat{c} y\\ 0 \emat \equiv \bmat{cc} T_... ...\cdot \bmat{c} y\\ 0 \emat = \bmat{c} T_ny\\ B_n y \emat$$

and

$$B_n = \bmat{ccccc} 0 & t_{n-1} & \ldots & t_2 & t_1 \\ t... ...ts & t_{n-1} \\ t_{-1} & t_{-2} & \ldots & t_{1-n}& 0 \emat.$$