Logo image
Back
Automatic derivation and implementation of fast convolution algorithms
Journal article   Open access   Peer reviewed

Automatic derivation and implementation of fast convolution algorithms

Jeremy R. Johnson and Anthony F. Breitzman
Journal of symbolic computation, v 37(2), pp 261-293
2004
DOI: https://doi.org/10.1016/j.jsc.2002.06.001
url
https://doi.org/10.1016/j.jsc.2002.06.001View
Published, Version of Record (VoR)Open Access (Publisher-Specific),  Open

Abstract

Convolution algorithms Cyclic convolution
This paper surveys algorithms for computing linear and cyclic convolution. Algorithms are presented in a uniform mathematical notation that allows automatic derivation, optimization, and implementation. Using the tensor product and Chinese remainder theorem, a space of algorithms is defined and the task of finding the best algorithm is turned into an optimization problem over this space of algorithms. This formulation led to the discovery of new algorithms with reduced operation count. Symbolic tools are presented for deriving and implementing algorithms.

Metrics

7 Record Views
5 citations in Web of Science
6 citations in Scopus

Details

InCites Highlights

Data related to this publication, from InCites Benchmarking & Analytics tool:

Web of Science research areas
Computer Science, Theory & Methods
Mathematics, Applied
Logo image