如何利用Toeplitz矩阵性质构造多项式M(x)以借助FFT计算矩阵向量乘积？

1. 明确矩阵M的结构 #

根据题目条件，M是托普利茨矩阵——所有沿主对角线平行的斜线上元素相等：

• 对任意下标i、j，若i-j=k，则M[i][j] = c_k，其中c_k是一个序列；
• 当k≥0（即i≥j）时，c_k = M[k][0]（取矩阵第一列的第k个元素）；
• 当k<0（即j>i）时，c_k = M[0][-k]（取矩阵第一行的第-k个元素）。

2. 构造对应多项式 #

无需将整个矩阵转化为多项式，只需基于托普利茨序列c构造适配多项式乘法的序列：

1. 生成长度为2n-1的序列C：将c序列向右平移n-1位，即对m∈[0, 2n-2]，$C[m] = c_{m-(n-1)}$。具体元素为：
   • $C[0] \sim C[n-2]$：对应第一行从右到左的元素$M[0][n-1], M[0][n-2], ..., M[0][1]$；
   • $C[n-1] = M[0][0]$；
   • $C[n] \sim C[2n-2]$：对应第一列从上到下的元素$M[1][0], M[2][0], ..., M[n-1][0]$。
2. 将序列C转为多项式：$C(x) = C[0] + C[1]x + C[2]x^2 + ... + C[2n-2]x^{2n-2}$。
3. 向量V对应的多项式：$V(x) = v_0 + v_1x + ... + v_{n-1}x^{n-1}$。

3. 关联卷积与矩阵乘法 #

计算C(x)与V(x)的多项式乘积（即线性卷积），得到结果序列D，其中$D[m]$是乘积中$x^m$项的系数：
$$D[m] = \sum_{k=0}^m C[k] \cdot V[m-k]$$
（当m-k超出V的下标范围时，$V[m-k]$视为0）

此时，MV的结果向量U的第i个元素（i∈[0, n-1]）恰好等于$D[n-1+i]$。以n=3为例：

• $U_0 = D[2] = M[0][0]v_0 + M[0][1]v_1 + M[0][2]v_2$
• $U_1 = D[3] = M[1][0]v_0 + M[0][0]v_1 + M[0][1]v_2$
• $U_2 = D[4] = M[2][0]v_0 + M[1][0]v_1 + M[0][0]v_2$
  完全匹配矩阵乘法的计算结果。

4. 时间复杂度分析 #

FFT算法可在$O(n \log n)$时间内完成两个长度为O(n)的多项式乘法：只需将序列补零至长度≥2n-1，执行FFT、点乘、逆FFT即可得到卷积结果。因此，MV的计算可通过FFT在$O(n \log n)$时间内完成。

内容的提问来源于stack exchange，提问作者SystemError