Convolution
Disambiguation: see also Polygon Convolution.
introduction
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 Operator
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