Gov*_*mar 6 algorithm performance fft matrix matrix-multiplication
O(n log n)Toeplitz矩阵和正确长度的矢量的乘积的算法是众所周知的:将其置于循环矩阵中,将其乘以矢量(和随后的零),并返回n乘积的顶部元素.
我发现很难找到最佳(时间)算法来乘以相同大小的两个Toeplitz矩阵.
任何人都可以给我一个算法吗？
这是一个O(n ^ 2)时间算法.
为了计算产品矩阵的一个对角线,我们需要计算长度为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等等.
如果您以浮点实现此功能,请注意灾难性取消.
| 归档时间： |
|
| 查看次数： |
4297 次 |
| 最近记录： |