Newsgroups: comp.parallel,sci.math.num-analysis
From: gross@noether.ucsc.edu (Mike Gross)
Subject: Re: Parallel Fourier transforms
Organization: University of California, Santa Cruz
Date: Mon, 18 Oct 1993 13:48:20 GMT

In comp.parallel I wrote:
>I need to solve Poisson's equation on an i860 supercomputer with local
>memory only. I would like to use Fourier transform methods to solve
>the equation, but it is not obvious to me how to perform a global operation
>such as a Fourier integral (or FFT) efficiently on data that must be fragmented
>across several processors. In order to get the dynamic range I need in my
>simulation, I require a space-domain mesh that is several times the size of
>local memory.

>Does anyone out there know of any good references for this problem? Or better
>yet, are there any publicly available routines? My problems sounds like one
>that has been attacked many times by parallel numerical analysts. I hope this
>isn't a FAQ.

I may be in a position to answer my own question, with a little help from
Michel Beland (beland@cerca.umontreal.ca), who provided a name from memory.
I did a citation search on that name, and also on the title words "parallel"
and "fourier." What came up was the following two articles:

Ganagi & Neelakantan
    Implementation of the Fast Fourier Transform Algorithm on a Parallel
Processor
    Current Science, 61(2), 105-108.

Tong & Swarztrauber
   Ordered Fast Fourier Transforms on a Massively Parallel Hypercube
Multiprocessor.
   Journal of Parallel & Distributed Computing 12(1), 50-59.

Both articles are from 1991. There is also a more recent reference, which I
haven't been able to decipher, from the folks at IBM Watson:

Christidis & Pattnaik
   Parallel Algorithm for the Fast Fourier Transform.
   EWECF Conference 13(4), 533-538.

Mike Gross
Physics Board
Univ of California                          GO SLUGS!!!!!
Santa Cruz, CA 95064
gross@physics.ucsc.edu