FFT ALGORITHMS AND THEIR ADAPTATION TO PARALLEL-PROCESSING

The development of the fast Fourier transform (FFT) and its numerous v ariants in the past 30 years has led to very efficient software and ha rdware implementations of the transform on uniprocessor computers. In recent years, many researchers have recognized the practical importanc e of minimizing computing time by parallelizing sequential FFT algorit hms in various ways for today's high-performance multiprocessor comput ers. This paper presents many FFT variants already proposed by others in a common framework, which illuminates the progress made in parallel izing them to this date, In addition, three new parallel FFT algorithm s along with communication complexity results are presented. The propo sed algorithms show alternative ways of designing parallel FFT algorit hms which feature reduced communication cost and further flexibility i n the choices of data mappings. (C) 1998 Elsevier Science Inc. All rig hts reserved.