A NEW MULTIDIMENSIONAL FAST CONVOLUTION ALGORITHM

This work introduces a new fast convolution-type technique for computi ng the multidimensional periodic convolutions of signals defined on ge neric lattices. The method presented does not evaluate multidimensiona l periodic convolutions via multidimensional FFT's but with an origina l algorithm. The major advantages of this technique are that it is mor e efficient than the well-known FFT-based fast convolution method and that its efficiency increases with the signal's dimensionality. One st riking indication of its computational efficiency is that the number o f operations per output point required by this method with nonseparabl e kernels of assigned dimensions is always smaller than the number of operations required by classical fast convolution algorithms with sepa rable kernels of identical dimensions.