Paper: Bluestein's FFT for arbitrary N on the hypercube

摘要: The original Cooley-Tukey FFT was published in 1965 and presented for sequences with length N equal to a power of two. However, the same paper they noted that their algorithm could be generalized composite which sequence product small primes. In 1967, Bergland an variants his mixed radix are currently wide use. 1968, Bluestein arbitrary including large N, Bluestein's not competitive Bergland's FFT. Since it is usually possible select did receive much attention. Nevertheless because its minimal communication requirements, may choice on multiprocessors, particularly those hypercube architecture. contrast FFT, pattern maps quite well onto hypercube. With P = 2^d processors, ordered requires 2d cycles packet N/2P comparable requirements two For fine-grain computations, 20log"2N computational cycles. Although this double required nevertheless preferred lower costs. most values also shown superior another alternative, namely parallel multiplication.