Automatic derivation and implementation of fast convolution algorithms

Jeremy R. Johnson, Anthony F. Breitzman

Research output: Contribution to journalArticlepeer-review

5 Scopus citations


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.

Original languageEnglish (US)
Pages (from-to)261-293
Number of pages33
JournalJournal of Symbolic Computation
Issue number2
StatePublished - Feb 2004

All Science Journal Classification (ASJC) codes

  • Algebra and Number Theory
  • Computational Mathematics


Dive into the research topics of 'Automatic derivation and implementation of fast convolution algorithms'. Together they form a unique fingerprint.

Cite this