结构化矩阵的快速矩阵-向量乘法

实践中经常出现依赖于O(n)参数的稠密矩阵。这些矩阵的例子包括

范德蒙矩阵：

V = \begin{bmatrix} 1 & 1 & \ldots & 1 \\ x_1 & x_2 & \ldots & x_n \\ x_1^2 & x_2^2 & \ldots & x_n^2 \\ \vdots & \vdots & \ddots & \vdots \\ x_1^{n-1} & x_2^{n-1} & \ldots & x_n^{n-1} \end{bmatrix},

托普利茨矩阵：

T = \begin{bmatrix} t_0 & t_{-1} & \ldots & t_{2-n} & t_{1-n} \\ t_1 & t_0 & t_{-1} & \ldots & t_{2-n} \\ \vdots & t_1 & t_0 & \ddots & \vdots \\ t_{n-2} & \vdots & \ddots & \ddots & t_{-1} \\ t_{n-1} & t_{n-2} & \ldots & t_1 & t_0 \end{bmatrix},

汉克尔矩阵： H = (H_{ij})=(c_{i+j}),

柯西矩阵： C = (C_{ij})=(\frac{1}{x_i-y_j}), 以及其他矩阵[257]。

这些矩阵及其逆矩阵可以以O(n\log^k n)时间复杂度与向量相乘，其中0 \leq k \leq 2，而不是O(n^2)或O(n^3)时间，具体取决于结构。这对于使用迭代求解器处理这些矩阵特别有用。迭代求解器在求解形如(A+B)x=b的系统时也很有用，其中A和B都是结构化的但属于不同的结构类别，或者如果A是结构化的而B是带状或稀疏的等。迭代方法在求解块系统时也很有用，当块是结构化矩阵但属于不同的结构类别，某些块也可能是稀疏的。例如，乘积

\begin{bmatrix}A & B \\C & 0 \end{bmatrix}\begin{bmatrix}x \\ y \end{bmatrix} =\begin{bmatrix}Ax+By \\ Cx \end{bmatrix},

其中A是对角的，B和C是托普利茨矩阵，可以在O(n\log n)时间内形成。

范德蒙矩阵及其逆矩阵可以以O(n\log^2 n)时间复杂度与向量相乘[196,195]。类似范德蒙矩阵及其逆矩阵也是如此，其中“-like”矩阵的定义见第§10.3.4节。托普利茨矩阵及其类似矩阵的矩阵-向量乘法使用快速傅里叶变换（FFT）需要O(n\log n)时间[198]。柯西矩阵-向量乘积Cz相当于在n个不同点x_1,x_2,\ldots,x_n上评估函数

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

可以通过使用快速多极方法在O(n)时间内完成[76,205]。

本节的其余部分展示了如何为托普利茨矩阵实现O(n\log n)的矩阵-向量乘法[198]。对于其他类别的结构化矩阵，我们参考[196]和[195]。

循环矩阵是一种特殊的托普利茨矩阵，形式为

C_n = \begin{bmatrix} a_0 & a_{-1} & \ldots &a_{2-n}& a_{1-n} \\ a_1 & a_0 & a_{-1} & \ldots & a_{2-n} \\ \vdots & a_1 & a_0 & \ddots & \vdots \\ a_{n-2} & \vdots & \ddots & \ddots & a_{-1} \\ a_{n-1} & a_{n-2} & \ldots & a_1 & a_0 \end{bmatrix},

其性质为a_{-k}=a_{n-k}，对于1\le k \le n-1。循环矩阵通过FFT对角化，即

C_n=F_n^* \cdot \mathrm{diag}(F_n a) \cdot F_n,

其中a=[a_0,a_1,\ldots,a_n]，F_n是傅里叶矩阵 F_n(j,k) = \frac{1}{\sqrt{n}} e^{-(j-1)(k-1)2 \pi \sqrt{-1}/n}。众所周知，F_n是酉矩阵，乘积F_n x可以在O(n\log n)时间内形成[453]。乘积y=C_n x也可以通过以下四个步骤在O(n\log n)时间内形成：

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

现在，如果T_n是一个托普利茨矩阵

T = \begin{bmatrix} t_0 & t_{-1} & \ldots & t_{2-n} & t_{1-n} \\ t_1 & t_0 & t_{-1} & \ldots & t_{2-n} \\ \vdots & t_1 & t_0 & \ddots & \vdots \\ t_{n-2} & \vdots & \ddots & \ddots & t_{-1} \\ t_{n-1} & t_{n-2} & \ldots & t_1 & t_0 \end{bmatrix},

那么乘积T_nx可以通过首先将T_n嵌入到一个2n\times 2n循环矩阵C_{2n}中，在O(n\log n)时间内计算，因为

C_{2n} \cdot\begin{bmatrix}y\\ 0\end{bmatrix}\equiv \begin{bmatrix}T_n & B_n \\ B_n & T_n\end{bmatrix}\cdot\begin{bmatrix}y\\ 0\end{bmatrix}= \begin{bmatrix}T_ny\\ B_n y\end{bmatrix}

并且

B_n = \begin{bmatrix}0 & t_{n-1} & \ldots & t_2 & t_1 \\ t_{1-n} & 0 & t_{n-1} & \ldots & t_2 \\ \vdots & t_{1-n} & 0 & \ddots & \vdots \\ t_{-2} & \vdots & \ddots & \ddots & t_{n-1} \\ t_{-1} & t_{-2} & \ldots & t_{1-n} & 0 \end{bmatrix}.