Copyrights to these papers may be held by the publishers. The download files are preprints. It is understood that all persons copying this information will adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

Lingchuan Meng, Jeremy Johnson, Franz Franchetti, Yevgen Voronenko, Marc Moreno Maza and Yuzhen Xie (Proc. Parallel Symbolic Computation (PASCO), pp. 169-170, 2010)
Spiral-Generated Modular FFT Algorithms
Preprint (366 KB)
Published paper (link to publisher)
Bibtex

This paper presents an extension of the Spiral system to automatically generate and optimize FFT algorithms for the discrete Fourier transform over finite fields. The generated code is intended to support modular algorithms for multivariate polynomial computations in the modpn library used by Maple. The resulting code provides an order of magnitude speedup over the original implementations in the modpn library, and the Spiral system provides the ability to automatically tune the FFT code to different computing platforms.

Keywords:
Fast Fourier Transform, SPIRAL, Algorithm, Code generator