分块矩阵的快速Fourier变换（FFT）在Toeplitz矩阵向量乘法中的应用
字数 3112 2025-12-06 12:55:59

分块矩阵的快速Fourier变换（FFT）在Toeplitz矩阵向量乘法中的应用

1. 问题描述
给定一个 \(n \times n\) 的Toeplitz矩阵 \(T\) 和一个向量 \(x \in \mathbb{R}^n\)，需要高效计算矩阵向量乘法 \(y = T x\)。

  • Toeplitz矩阵：矩阵的每条对角线上的元素相同，即 \(T_{i,j} = t_{i-j}\)，其中 \(t_k\) 是常数。
  • 直接计算 \(y = T x\) 需要 \(O(n^2)\) 次运算。但利用Toeplitz矩阵的结构，可通过嵌入为循环矩阵，结合快速傅里叶变换（FFT） 将复杂度降为 \(O(n \log n)\)。

2. 关键思想

  • Toeplitz矩阵可以“嵌入”到一个更大的循环矩阵中。
  • 循环矩阵与向量的乘法可通过FFT在 \(O(m \log m)\) 时间内完成（\(m\) 是循环矩阵的维数）。
  • 从循环矩阵乘法结果中提取部分，即得Toeplitz矩阵的乘法结果。

3. 具体步骤

步骤1：构造循环矩阵
设 \(T\) 是 \(n \times n\) 的Toeplitz矩阵，其第一列为 \(c = (t_0, t_1, \dots, t_{n-1})^\top\)，第一行为 \(r = (t_0, t_{-1}, \dots, t_{-(n-1)})^\top\)（注意 \(t_0\) 相同）。
构造一个 \(m \times m\) 的循环矩阵 \(C\)，其中 \(m \geq 2n-1\)（通常取 \(m=2n\) 以便FFT高效计算）。
循环矩阵 \(C\) 的第一列 \(c_{\text{circ}}\) 由以下方式组成：

\[c_{\text{circ}} = (t_0, t_1, \dots, t_{n-1}, 0, \dots, 0, t_{-(n-1)}, \dots, t_{-1})^\top \]

即：前 \(n\) 个元素为 \(T\) 的第一列 \(c\)，接着 \(m-2n+1\) 个零（当 \(m>2n-1\) 时），最后 \(n-1\) 个元素为 \(T\) 第一行的后 \(n-1\) 个元素（倒序排列）。
例如，若 \(n=3\)，\(T = \begin{bmatrix} t_0 & t_{-1} & t_{-2} \\ t_1 & t_0 & t_{-1} \\ t_2 & t_1 & t_0 \end{bmatrix}\)，取 \(m=6\)，则：

\[c_{\text{circ}} = (t_0, t_1, t_2, 0, t_{-2}, t_{-1})^\top \]

循环矩阵 \(C\) 完全由 \(c_{\text{circ}}\) 决定，其每一列是前一列的循环下移。

步骤2：构造扩展向量
将输入向量 \(x \in \mathbb{R}^n\) 扩展为 \(m\) 维向量 \(x_{\text{ext}}\)：

\[x_{\text{ext}} = (x_1, x_2, \dots, x_n, 0, 0, \dots, 0)^\top \]

后 \(m-n\) 个元素补零。

步骤3：利用FFT计算循环矩阵乘法
循环矩阵 \(C\) 可被傅里叶矩阵对角化：

\[C = F_m^{-1} \cdot \text{diag}(\lambda) \cdot F_m \]

其中 \(F_m\) 是 \(m \times m\) 的离散傅里叶变换（DFT）矩阵，\(\lambda = F_m \, c_{\text{circ}}\) 是 \(C\) 的特征值组成的向量。
于是，矩阵向量乘法 \(C x_{\text{ext}}\) 可快速计算：

  1. 计算 \(\lambda = \text{FFT}(c_{\text{circ}})\)。
  2. 计算 \(u = \text{FFT}(x_{\text{ext}})\)。
  3. 计算逐点乘积 \(v = \lambda \odot u\)（\(\odot\) 表示逐元素相乘）。
  4. 计算逆FFT：\(y_{\text{ext}} = \text{IFFT}(v)\)。
    此时 \(y_{\text{ext}} = C x_{\text{ext}}\)，计算复杂度为 \(O(m \log m)\)。

步骤4：提取Toeplitz矩阵乘法结果
由于构造时保证了 \(C\) 的左上 \(n \times n\) 子矩阵等于 \(T\)，且 \(x_{\text{ext}}\) 前 \(n\) 个元素为 \(x\)，后补零，因此 \(y_{\text{ext}}\) 的前 \(n\) 个元素就是 \(T x\)：

\[y = (y_{\text{ext}})_1 : (y_{\text{ext}})_n \]

即取 \(y_{\text{ext}}\) 的前 \(n\) 个分量。

4. 算法复杂度分析

  • 主要计算量：三次FFT/IFFT，每次 \(O(m \log m)\)，以及一次逐点乘法 \(O(m)\)。
  • 由于 \(m = O(n)\)（通常取 \(m=2n\) 或稍大的2的幂），总复杂度为 \(O(n \log n)\)，远优于直接计算的 \(O(n^2)\)。

5. 示例演示
设 \(n=3\)，

\[T = \begin{bmatrix} 4 & 2 & 1 \\ 3 & 4 & 2 \\ 5 & 3 & 4 \end{bmatrix},\quad x = (1, 2, 3)^\top \]

  1. 构造 \(c_{\text{circ}} = (4, 3, 5, 0, 1, 2)^\top\)（取 \(m=6\)，注意 \(t_{-2}=1, t_{-1}=2\) 放在末尾）。
  2. 构造 \(x_{\text{ext}} = (1, 2, 3, 0, 0, 0)^\top\)。
  3. 用FFT计算：
    • \(\lambda = \text{FFT}(c_{\text{circ}})\)，
    • \(u = \text{FFT}(x_{\text{ext}})\)，
    • \(v = \lambda \odot u\)，
    • \(y_{\text{ext}} = \text{IFFT}(v)\)。
  4. 取前3个分量：
    \(y_{\text{ext}} \approx (11, 19, 23, \dots)^\top \Rightarrow y = (11, 19, 23)^\top\)。
    验证直接乘法：
    \(T x = (4\cdot1+2\cdot2+1\cdot3, 3\cdot1+4\cdot2+2\cdot3, 5\cdot1+3\cdot2+4\cdot3) = (11, 19, 23)\)，结果一致。

6. 应用与扩展

  • 该方法广泛用于求解Toeplitz线性方程组（结合迭代法或预处理技术）。
  • 可推广到分块Toeplitz矩阵（每个块是Toeplitz矩阵）的向量乘法，通过二维FFT加速。
  • 在信号处理、时间序列分析中，Toeplitz矩阵常出现在自相关矩阵中，FFT加速至关重要。

总结：利用Toeplitz矩阵可嵌入循环矩阵的性质，将矩阵向量乘法转化为循环卷积，再通过FFT高效计算，显著降低计算复杂度。

分块矩阵的快速Fourier变换（FFT）在Toeplitz矩阵向量乘法中的应用 1. 问题描述 给定一个 \(n \times n\) 的 Toeplitz矩阵 \(T\) 和一个向量 \(x \in \mathbb{R}^n\)，需要高效计算矩阵向量乘法 \(y = T x\)。 Toeplitz矩阵 ：矩阵的每条对角线上的元素相同，即 \(T_ {i,j} = t_ {i-j}\)，其中 \(t_ k\) 是常数。 直接计算 \(y = T x\) 需要 \(O(n^2)\) 次运算。但利用Toeplitz矩阵的结构，可通过 嵌入为循环矩阵 ，结合 快速傅里叶变换（FFT） 将复杂度降为 \(O(n \log n)\)。 2. 关键思想 Toeplitz矩阵可以“嵌入”到一个更大的 循环矩阵 中。 循环矩阵与向量的乘法可通过FFT在 \(O(m \log m)\) 时间内完成（\(m\) 是循环矩阵的维数）。 从循环矩阵乘法结果中提取部分，即得Toeplitz矩阵的乘法结果。 3. 具体步骤 步骤1：构造循环矩阵 设 \(T\) 是 \(n \times n\) 的Toeplitz矩阵，其第一列为 \(c = (t_ 0, t_ 1, \dots, t_ {n-1})^\top\)，第一行为 \(r = (t_ 0, t_ {-1}, \dots, t_ {-(n-1)})^\top\)（注意 \(t_ 0\) 相同）。 构造一个 \(m \times m\) 的循环矩阵 \(C\)，其中 \(m \geq 2n-1\)（通常取 \(m=2n\) 以便FFT高效计算）。 循环矩阵 \(C\) 的第一列 \(c_ {\text{circ}}\) 由以下方式组成： \[ c_ {\text{circ}} = (t_ 0, t_ 1, \dots, t_ {n-1}, 0, \dots, 0, t_ {-(n-1)}, \dots, t_ {-1})^\top \] 即：前 \(n\) 个元素为 \(T\) 的第一列 \(c\)，接着 \(m-2n+1\) 个零（当 \(m>2n-1\) 时），最后 \(n-1\) 个元素为 \(T\) 第一行的后 \(n-1\) 个元素（倒序排列）。 例如，若 \(n=3\)，\(T = \begin{bmatrix} t_ 0 & t_ {-1} & t_ {-2} \\ t_ 1 & t_ 0 & t_ {-1} \\ t_ 2 & t_ 1 & t_ 0 \end{bmatrix}\)，取 \(m=6\)，则： \[ c_ {\text{circ}} = (t_ 0, t_ 1, t_ 2, 0, t_ {-2}, t_ {-1})^\top \] 循环矩阵 \(C\) 完全由 \(c_ {\text{circ}}\) 决定，其每一列是前一列的循环下移。 步骤2：构造扩展向量 将输入向量 \(x \in \mathbb{R}^n\) 扩展为 \(m\) 维向量 \(x_ {\text{ext}}\)： \[ x_ {\text{ext}} = (x_ 1, x_ 2, \dots, x_ n, 0, 0, \dots, 0)^\top \] 后 \(m-n\) 个元素补零。 步骤3：利用FFT计算循环矩阵乘法 循环矩阵 \(C\) 可被傅里叶矩阵对角化： \[ C = F_ m^{-1} \cdot \text{diag}(\lambda) \cdot F_ m \] 其中 \(F_ m\) 是 \(m \times m\) 的离散傅里叶变换（DFT）矩阵，\(\lambda = F_ m \, c_ {\text{circ}}\) 是 \(C\) 的特征值组成的向量。 于是，矩阵向量乘法 \(C x_ {\text{ext}}\) 可快速计算： 计算 \(\lambda = \text{FFT}(c_ {\text{circ}})\)。 计算 \(u = \text{FFT}(x_ {\text{ext}})\)。 计算逐点乘积 \(v = \lambda \odot u\)（\(\odot\) 表示逐元素相乘）。 计算逆FFT：\(y_ {\text{ext}} = \text{IFFT}(v)\)。 此时 \(y_ {\text{ext}} = C x_ {\text{ext}}\)，计算复杂度为 \(O(m \log m)\)。 步骤4：提取Toeplitz矩阵乘法结果 由于构造时保证了 \(C\) 的左上 \(n \times n\) 子矩阵等于 \(T\)，且 \(x_ {\text{ext}}\) 前 \(n\) 个元素为 \(x\)，后补零，因此 \(y_ {\text{ext}}\) 的前 \(n\) 个元素就是 \(T x\)： \[ y = (y_ {\text{ext}}) 1 : (y {\text{ext}}) n \] 即取 \(y {\text{ext}}\) 的前 \(n\) 个分量。 4. 算法复杂度分析 主要计算量：三次FFT/IFFT，每次 \(O(m \log m)\)，以及一次逐点乘法 \(O(m)\)。 由于 \(m = O(n)\)（通常取 \(m=2n\) 或稍大的2的幂），总复杂度为 \(O(n \log n)\)，远优于直接计算的 \(O(n^2)\)。 5. 示例演示 设 \(n=3\)， \[ T = \begin{bmatrix} 4 & 2 & 1 \\ 3 & 4 & 2 \\ 5 & 3 & 4 \end{bmatrix},\quad x = (1, 2, 3)^\top \] 构造 \(c_ {\text{circ}} = (4, 3, 5, 0, 1, 2)^\top\)（取 \(m=6\)，注意 \(t_ {-2}=1, t_ {-1}=2\) 放在末尾）。 构造 \(x_ {\text{ext}} = (1, 2, 3, 0, 0, 0)^\top\)。 用FFT计算： \(\lambda = \text{FFT}(c_ {\text{circ}})\)， \(u = \text{FFT}(x_ {\text{ext}})\)， \(v = \lambda \odot u\)， \(y_ {\text{ext}} = \text{IFFT}(v)\)。 取前3个分量： \(y_ {\text{ext}} \approx (11, 19, 23, \dots)^\top \Rightarrow y = (11, 19, 23)^\top\)。 验证直接乘法： \(T x = (4\cdot1+2\cdot2+1\cdot3, 3\cdot1+4\cdot2+2\cdot3, 5\cdot1+3\cdot2+4\cdot3) = (11, 19, 23)\)，结果一致。 6. 应用与扩展 该方法广泛用于求解 Toeplitz线性方程组 （结合迭代法或预处理技术）。 可推广到 分块Toeplitz矩阵 （每个块是Toeplitz矩阵）的向量乘法，通过二维FFT加速。 在信号处理、时间序列分析中，Toeplitz矩阵常出现在自相关矩阵中，FFT加速至关重要。 总结 ：利用Toeplitz矩阵可嵌入循环矩阵的性质，将矩阵向量乘法转化为循环卷积，再通过FFT高效计算，显著降低计算复杂度。