TY - JOUR
T1 - Automatic derivation and implementation of fast convolution algorithms
AU - Johnson, Jeremy R.
AU - Breitzman, Anthony F.
N1 - Copyright:
Copyright 2017 Elsevier B.V., All rights reserved.
PY - 2004/2
Y1 - 2004/2
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=1942477516&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=1942477516&partnerID=8YFLogxK
U2 - 10.1016/j.jsc.2002.06.001
DO - 10.1016/j.jsc.2002.06.001
M3 - Article
AN - SCOPUS:1942477516
VL - 37
SP - 261
EP - 293
JO - Journal of Symbolic Computation
JF - Journal of Symbolic Computation
SN - 0747-7171
IS - 2
ER -