Вы уверены, что хотите использовать БПФ? Это будет преобразование целого массива, которое будет дорогим. Если вы уже выбрали сверточный фильтр 9x9, вам не нужно использовать БПФ.
Как правило, самый дешевый способ сделать свертку в C - это создать цикл, который перемещает указатель на массив, суммируя свернутые значения в каждой точке и записывая данные в новый массив. Затем этот цикл можно распараллелить, используя ваш любимый метод (векторизация компилятора, библиотеки MPI, OpenMP и т. Д.).
Относительно границ:
- Если вы предполагаете, что значения равны 0 за пределами границ, то добавьте 4-элементную границу 0 к вашему 2d массиву точек. Это позволит избежать необходимости использования операторов if для обработки границ, которые дороги.
- Если ваши данные переносятся по границам (то есть периодически), используйте модуль по модулю или добавьте 4-элементную границу, которая копирует противоположную сторону сетки (abcdefg -> fgabcdefgab для 2 точек). ** Примечание: это то, что вы неявно предполагаете при любом виде преобразования Фурье, включая БПФ **. Если это не так, вам нужно будет учесть это, прежде чем выполнять БПФ.
4 балла связаны с тем, что максимальное перекрытие границ ядра 9x9 составляет 4 балла за пределами основной сетки. Таким образом, для ядра 2n + 1 x 2n + 1 необходимо n точек границы.
Если вам нужно, чтобы эта свертка была действительно быстрой, и / или ваша сетка велика, рассмотрите возможность ее разбиения на более мелкие части, которые можно хранить в кеше процессора и, таким образом, вычислять намного быстрее. Это также относится к любой разгрузке GPU, которую вы, возможно, захотите сделать (они идеально подходят для такого типа вычислений с плавающей запятой).