Fast Fourier transforms for the evaluation of convolution products: CPU versus GPU implementation
Authors:
- 18 December 2013
- journal article
- research article
- Published by Wiley in International Journal of Numerical Modelling: Electronic Networks, Devices and Fields
- Vol. 27 (3) , 495-504
Abstract
SUMMARY: In a large variety of research areas, convolution products that relate a physical quantity in some observation points with their sources are encountered. When the sources and the observation points coincide, the numerical evaluation of the physical quantity typically leads to order N2 numerical problems. Here, fast Fourier transforms are widely used to reduce the computations to order Nlog N complexity. When adopting Fourier transforms (FFT) for finite physical problems, zero padding is required. Hence, in 2D and 3D problems, an optimization of the evaluation of the convolution product includes a non‐execution of Fourier transforms on arrays containing only zeros in the forward 2D or 3D FFT scheme and their corresponding arrays in the inverse 2D or 3D FFT scheme. This paper describes the implementation of such an approach on graphical processing units (GPUs) and compares the time gains on GPU and on CPU. It is found that on CPU, the speedup corresponds with the theoretical limit, while in the GPU implementation, the memory bandwidth limits the speedup ratio. Copyright © 2013 John Wiley & Sons, Ltd.Keywords
This publication has 17 references indexed in Scilit:
- Acceleration of a QM/MM‐QMC simulation using GPUJournal of Computational Chemistry, 2011
- Fast evaluation of Helmholtz potential on graphics processing units (GPUs)Journal of Computational Physics, 2010
- An efficient algorithm for classical density functional theory in three dimensions: Ionic solutionsThe Journal of Chemical Physics, 2010
- An FFT-Accelerated Time-Domain Multiconductor Transmission Line SimulatorIEEE Transactions on Electromagnetic Compatibility, 2010
- An Implementation of the Smooth Particle Mesh Ewald Method on GPU HardwareJournal of Chemical Theory and Computation, 2009
- Fast convolution with the free space Helmholtz Green’s functionJournal of Computational Physics, 2009
- A Full-Wave 2.5D Volume Integral Equation Solver for 3D Millimeter-Wave Scattering by Large Inhomogeneous 2D ObjectsIEEE Transactions on Antennas and Propagation, 2009
- Rapid Solution of the Wave Equation in Unbounded DomainsSIAM Journal on Numerical Analysis, 2009
- An FFT-based signal identification approach for obtaining the propagation constants of the leaky modes in layered mediaAEU - International Journal of Electronics and Communications, 2004
- A Weak Form of the Conjugate Gradient FFT Method for Two-Dimensional ElastodynamicsJournal of Computational Physics, 2000