Conference proceeding
Generating Symmetric DFTs and Equivariant FFT Algorithms
ISSAC 2007: PROCEEDINGS OF THE 2007 INTERNATIONAL SYMPOSIUM ON SYMBOLIC AND ALGEBRAIC COMPUTATION, pp 195-202
01 Jan 2007
Abstract
This paper presents a code generator which produces efficient implementations of multi-dimensional fast Fourier transform (FFT) algorithms which utilize symmetries in the input data to reduce memory usage and the number of arithmetic operations. The FFT algorithms axe constructed using a group theoretic version of the divide and conquer step in the FFT that is compatible with the group of symmetries. The GAP compute algebra system is used to perform the necessary group computations and the generated algorithm is represented as a symbolic matrix factorization, which is translated into efficient code using the SPIRAL system. Performance data is given that shows that the resulting code is significantly faster than state-of-the-art FFT implementations that do not utilize the symmetries.
Metrics
Details
- Title
- Generating Symmetric DFTs and Equivariant FFT Algorithms
- Creators
- Jeremy Johnson - Drexel UniversityXu Xu - Drexel University
- Contributors
- C W Brown (Editor)
- Publication Details
- ISSAC 2007: PROCEEDINGS OF THE 2007 INTERNATIONAL SYMPOSIUM ON SYMBOLIC AND ALGEBRAIC COMPUTATION, pp 195-202
- Conference
- ISSAC 2007 INTERNATIONAL SYMPOSIUM ON SYMBOLIC AND ALGEBRAIC COMPUTATION
- Publisher
- Assoc Computing Machinery
- Number of pages
- 8
- Resource Type
- Conference proceeding
- Language
- English
- Academic Unit
- Computer Science
- Web of Science ID
- WOS:000265926900027
- Scopus ID
- 2-s2.0-36348945220
- Other Identifier
- 991019170478404721
InCites Highlights
Data related to this publication, from InCites Benchmarking & Analytics tool:
- Web of Science research areas
- Computer Science, Theory & Methods
- Mathematics, Applied