两个托普利茨矩阵的乘积？

Question

托普利茨矩阵和正确长度的向量乘积的

O(n log n)

算法是众所周知的：将其放入循环矩阵中，将其乘以向量（以及后续的零），然后返回顶部

n

产品的元素。

我发现很难找到最佳（时间方面）算法来将两个相同大小的托普利茨矩阵相乘。

任何人都可以给我一个算法吗？

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 条目减去

ij

加

dp

。 3,3 条目是

cq + dp + eo + fm + gl

，或者 2,2 条目减去

hk

加

cq

。 4,4 条目是

br + cq + dp + eo + fm

等

如果您以浮点实现此操作，请注意灾难性取消。