Convolution
Disambiguation: see also polygon-convolution
Convolution (see wikipedia) is used in the GeoDms to calculate a neighbourhood-potential using an input grid with n*m elements and a kernel of k*j elements, see the description of the potential function.
The GeoDms utilizes the IPP 7.0 library convolution functions ippsConv_16s_Sfs, ippsConv_32f, ippsConv_64f in the OperPot.cpp code unit as default implementation for potential calculations. These functions perform an FFT on both their input arrays of size N, then multiply the spectra element-wize and then reverse-FFT the product to generate the requested result. The IPP 7.0 library also utilizes multiple cores when present and available, still available as potentialSlow for comparison. This results in a O(N*log(N)) operation, whereas the classical naive implementation with four nested loops requires O(n*m*k*j) operations.
To make this possible, the 2D n * m grid and k * j grid are translated to two uniform signals of N = (n+k−1) * (m+j−1) elements each with appropriate zero-padding.
The resulting grid can sometimes contain small round-off errors resulting from different frequencies that have to cancel-out, especially in empty zero-valued regions sometimes very small values occur, sometimes even negative when all input is non-negative. In order to remove these undesired artifacts, a smoothing post-processing is performed by default that resets to zero all values that are nearer to zero than $\sqrt{\sum\limits_i(v_i^2) \over 1000000000.0}$. The potential_raw operations does not perform this post-processing.
ToDo
Investigate FFTW as substitute for IPPS 7.0