Skip to main content
Article
Automatic derivation and implementation of fast convolution algorithms
Journal of Symbolic Computation (2004)
  • Jeremy R. Johnson, Drexel University
  • Dr. Anthony Breitzman, Rowan University
Abstract
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
Keywords
  • Cyclic convolution,
  • Convolution algorithms
Disciplines
Publication Date
2004
DOI
10.1016/j.jsc.2002.06.001
Citation Information
Jeremy R. Johnson and Anthony Breitzman. "Automatic derivation and implementation of fast convolution algorithms" Journal of Symbolic Computation Vol. 37 Iss. 2 (2004) p. 261 - 293
Available at: http://works.bepress.com/anthony-breitzman/20/