Symbolic Computation Group

David R. Cheriton School of Computer Science
University of Waterloo, Waterloo, Ontario, Canada

Generating Symmetric FFT Algorithms
Jeremy Johnson, Drexel University, Philadelphia, USA
Friday, November 3, 2006, at U. of Western Ontario.


This talk is centered around two challanges for symbolic mathematical software and is organized into two parts. The first challenge is to use mathematical structure and symbolic mathematical computation to generate high-performance code - the challenge is to produce adaptable code that is competetive with highly tuned vendor implementations. The second challenge is to provide a high-level interface where mathematical algorithms, denoted in the appropriate mathematical abstraction, are easily specified and the details automatically derived.

The first part presents an overview of the SPIRAL system ( for generating, optimizing, and automatically adapting to different platforms high-performance implementations of fast signal transforms such as the Fast Fourier Transform (FFT), discrete trigonometric transforms, fast wavelet transform, and filtering. Algorithms are represented as mathematical formulas and algorithms are derived and manipulated using rewrite rules. The selection of algorithm and implementation strategy are guided by a feedback loop which uses intelligent search to find the best implementation on a given platform. Performance data for the FFT is shown illustrating that the code generated is competitive with vendor supplied code (Intel's MKL and IPP libraries) and alternative approaches such as FFTW. In cases where the vendor was unable to spend sufficient time tuning, the SPIRAL generated code is significantly faster.

The second part presents a new algorithm, generalizing the real FFT, for computing the multi-dimensional discrete Fourier transform of an input vector having symmetric data. The algorithm uses a divide and conquer approach similar to the standard FFT, but improves the constant by avoiding the redundant computation presented by the symmetric data. This algorithm is most naturally stated and derived abstractly using FFTs of finite Abelian groups. The symmetries of a function defined on the group A, are described by a subgroup of the semi-direct product of the automorphism group of A and the Heisenberg group of A, and the algorithm is obtained from the action of the affine part of this group on the indexing set given by A. This level of abstraction makes the algorithm easy to describe and derive, but difficult to implement due to the many details the abstraction hides. We present, preliminary software, written in the computer algebra system GAP, designed to build on top of SPIRAL, for generating concrete symmetric FFT algorithms, described by matrix factorizations, from the abstract formulation.


Jeremy R. Johnson joined Drexel University in 1991 after receiving his Ph.D. in Computer and Information Science from the Ohio State University. He obtained a B.A. in Mathematics (with honors) from the University of Wisconsin at Madison in 1985 and an M.S. in computer and information science from the University of Delaware in 1988.

He is currently serving as Department Head for the Department of Computer Science and holds a joint appointment in the Department of Electrical and Computer Engineering. He has held visiting positions in the Department of Electrical and Computer Engineering at Carnegie Mellon University and the Research Institute for Symbolic Computation in Linz Austria.

Dr. Johnson's research interests include algebraic algorithms, computer algebra systems, problem solving environments, programming languages and compilers, high performance computing, hardware generation, and automated performance tuning. He is currently working on SPIRAL, a joint research project with Carnegie Mellon University and the University of Illinois at Urbana-Champaign, funded by DARPA and NSF, to develop techniques to automatically implement and optimize signal processing algorithms. He co-edited a special issue of the Journal of Symbolic Computation devoted to Computer Algebra and Signal Processing, and is a member of the editorial board of the Journal of Applicable Algebra in Engineering, Communication and Computing. He is co-director, with Prawat Nagvajara of the Application Specific Computing Research Group with application projects in signal processing and power systems. He is also co-director, with Bruce Char and Werner Krandick, of the Applied Symbolic Computing (ASYM) Research Group.


Last modified on Sunday, 04 November 2012, at 15:42 hours.