两个Toeplitz矩阵的乘积？

Question

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

我发现很难找到最好的(时间)算法来乘以两个相同大小的Toeplitz矩阵。

谁能给我一个解决这个问题的算法？

Answer 1

这是一个O(n^2)-time算法。

为了计算乘积矩阵的对角线之一，我们需要计算长度为n的窗口上的点积，这些窗口的长度为-(2n-1)个列表，这些列表是以锁步方式滑动的。两个连续条目之间的差异可以在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等。

如果你是用浮点数实现的，请注意catastrophic cancellation。