Parallel Three-Dimensional Nonequispaced Fast Fourier Transforms and Their Application to Particle Simulation
| Autor: | Michael Pippig, Daniel Potts |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2012 |
| Předmět: |
ddc:518
Computer science 65T50 65Y05 Applied Mathematics Computation Fast Fourier transform Parallel algorithm parallel nonequispaced Fourier transform fast summation particle mesh FFT NFFT Parallel computing Computational science Computational Mathematics Scalability parallel nichtäquidistant Fourier-Transformation schnelle summation FFT NFFT Distributed memory Boundary value problem ddc:004 Massively parallel Schnelle Fourier-Transformation Paralleler Algorithmus Parallelverarbeitung MPI P system |
| Popis: | Starting from an approved serial algorithm, we develop a new parallel algorithm for calculating nonequispaced fast Fourier transforms on massively parallel distributed memory ar- chitectures. We demonstrate how to deal with the inherent load imbalance of the serial algorithm due to the use of oversampled FFT. This algorithm has been implemented in a new open source software library called PNFFT. Furthermore, we derive a new parallel distributed memory algorithm for the fast computation of fully Coulomb interactions in a charged particle system with nonperiodic boundary conditions based on a particle-mesh approximation scheme. We show that an appropri- ate adjustment of the underlying parallel nonequispaced fast Fourier transform circumvents severe load imbalance due to particle scaling. To prove the high scalability of our algorithms we provide performance results on a BlueGene/P system using up to 65536 cores. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|