如何使用快速傅立叶变换来执行矩阵的卷积？

Question

我需要添加很多大型3D阵列（与500x500x500形状）组合在一起，想在傅立叶空间用乘法来加快这一进程。问题是，相比于简单地把矩阵的傅立叶空间乘以当我没有得到相同的答案。

为了测试它，我写了一个小例子，试图使它工作，但答案是不是我的预期。无论是我的数学知识是错误的或者我没有正确使用该功能。

下面是最简单的代码显示什么，我试图做的：

import numpy as np

c = np.asarray(((1,2),(2,3)))
d = np.asarray(((1,4),(1,5)))

print("Transform")
Nc = np.fft.rfft2(c)
Nd = np.fft.rfft2(d)

print("Inverse")
Nnc = np.fft.irfft2(Nc)
Nnd = np.fft.irfft2(Nd)

print("Somme")
S = np.dot(Nc, Nd)
print(np.fft.irfft2(S))

当我打印S，我得到的结果是：

[[6, 28],[10,46]]

但是，从我的理解对傅立叶空间，乘将意味着除了傅立叶空间之外，所以我应该得到S = c + d？

我使用FFT功能做错事或者是我的假设是s应等于C以及d错了吗？

Answer 1

这里有一个小误会：

乘法傅立叶空间相当于在空间域，而不是除了convolution。

有没有办法加快除了以这种方式。

Answer 2

如果你想通过傅立叶域计算c+d，你必须添加的两个频谱，而不是将它们相乘：

np.fft.irfft2(Nc+Nd) == c+d  # (up to numerical precision)

当然，这比简单地在空间域中将所述矩阵慢得多。

如@Florian said，它是卷积可以通过在空间域中相乘来加快。