计算 Toeplitz 矩阵和正确长度的向量的乘积的 O(n log n) 算法是众所周知的:将其放入循环矩阵中，将其乘以向量 (和后续的零)，并返回产品的前 n 个元素。
我发现很难找到将两个相同大小的 Toeplitz 矩阵相乘的最佳(时间方面)算法。
谁能给我一个算法？
最佳答案
这是一个 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 条目减去 ij 加上 dp。 3,3 条目是 cq + dp + eo + fm + gl，或者 2,2 条目减去 hk 加上 cq。 4,4条目是br + cq + dp + eo + fm等
如果你在 float 中实现它，请注意 catastrophic cancellation .
关于performance - 两个 Toeplitz 矩阵的乘积？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/15889521/