Как использовать быстрое преобразование Фурье для выполнения свертки матрицы?

Question

Мне нужно сложить много больших трехмерных массивов (размером 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

Если вы хотите вычислить c+d через область Фурье, вам нужно добавить два спектра, а не умножить их:

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

Конечно, это намного медленнее, чем простое добавлениематрицы в пространственной области.

Как сказал @ Флориан , это свертка, которая может быть ускорена путем умножения в пространственной области.

Answer 2

Здесь есть небольшое недоразумение:

Умножение в пространстве Фурье соответствует свертке в пространственной области, а не сложению.

Нет способа ускорить сложение таким способом.