performance - 两个 Toeplitz 矩阵的乘积？

Question

Toeplitz 矩阵和正确长度向量的O(n log n)乘积算法是众所周知的：将其放入循环矩阵中，乘以向量（以及随后的零），然后返回n乘积的顶部元素。

我很难找到将两个相同大小的 Toeplitz 矩阵相乘的最佳（时间）算法。

谁能给我一个算法？

Answer 1

这是一个 O(n^2) 时间的算法。

为了计算乘积矩阵的对角线之一，我们需要在长度为 (2n-1) 的列表中以锁步滑动的长度为 n 的窗口上计算点积。两个连续条目之间的差异可以在 O(1) 时间内计算出来。

例如，考虑乘积

e f g h i    o p q r s
d e f g h    m o p q r
c d e f g    l m o p q
b c d e f    k l m o p
a b c d e    j k l m o

1,1 条目是eo + fm + gl + hk + ij. 2,2 项是dp + eo + fm + gl + hk，或 1,1 项减去ijplus dp。3,3 项是cq + dp + eo + fm + gl，或 2,2 项减去hkplus cq。4,4 条目是br + cq + dp + eo + fm等。

如果您在浮点中实现这一点，请注意灾难性取消。