A PARALLEL FAST FOURIER TRANSFORM

Silvia Morante (), Giancarlo Rossi and Gaetano Salina
Additional contact information
Silvia Morante: Dipartimento di Fisica, Università di Roma Tor Vergata, INFM, Unità di Tor Vergata, INFN, Sezione di Roma 2, Via della Ricerca Scientifica, 00133 Roma, Italy
Giancarlo Rossi: Dipartimento di Fisica, Università di Roma Tor Vergata, INFN, Sezione di Roma 2, Via della Ricerca Scientifica, 00133 Roma, Italy
Gaetano Salina: INFN, Sezione di Roma 2, Via della Ricerca Scientifica, 00133 Roma, Italy

International Journal of Modern Physics C (IJMPC), 1999, vol. 10, issue 05, 781-805

Abstract: In this paper we discuss the general problem of implementing the multidimensional Fast Fourier Transform algorithm on parallel computers. We show that, on a machine withPprocessors and fully parallel node communications, the optimal asymptotic scaling behavior of the total computational time with the number of data points,N, given inddimensions by the formulaaN/Plog(N/P)+bN/P(d-1)/d, can actually be achieved on realistic platforms. As a concrete realization of our strategy, we have produced codes efficiently running on machines of the APE family and on Cray T3E. On the former for asymptotic values ofNour codes attain the above optimal result.

Keywords: Fourier transform; Parallel computing (search for similar items in EconPapers)
Date: 1999
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.worldscientific.com/doi/abs/10.1142/S0129183199000607
Access to full text is restricted to subscribers

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wsi:ijmpcx:v:10:y:1999:i:05:n:s0129183199000607

Ordering information: This journal article can be ordered from

DOI: 10.1142/S0129183199000607

Access Statistics for this article

International Journal of Modern Physics C (IJMPC) is currently edited by H. J. Herrmann

More articles in International Journal of Modern Physics C (IJMPC) from World Scientific Publishing Co. Pte. Ltd.
Bibliographic data for series maintained by Tai Tone Lim ().