Automatic Derivation and Implementation of Fast Convolution Algorithms Anthony Breitzman and Jeremy Johnson Drexel University Email: abreitz@chiresearch.com, jjohnson@mcs.drexel.edu Abstract: We discuss a Maple package created for exploring the techniques of Winograd, Nussbaumer, and others for computing "fast" convolution algorithms. By codifying known convolution techniques into a common framework of bilinear algorithms built from parameterized matrices and algebraic operators, we are able to use Maple's symbolic and algebraic computation facilities to derive and manipulate these algorithms. The infrastructure provided by the package allows us to generate, manipulate, test, and combine various convolution algorithms all within in an interactive environment. The algorithms generated by the package can be exported to a domain-specific language called SPL (Signal Processing Language) and then translated into efficient C or FORTRAN code by the SPL compiler. By combining the strengths of Maple and the SPL compiler one gets the benefits of existing algebraic computation tools without the need to embed high-performance compiler technology in a computer algebra system. The resulting environment allows one to systematically apply the algebraic theory developed over the years to produce correct and efficient programs. Numerous algorithmic choices can be tried, allowing the user to rapidly test various optimizations to find the best combination of algorithms for a particular size convolution on a particular computer. Furthermore, automatic code generation and algebraic verification provides the ability to construct non-trivial examples with confidence that the resulting code is correct.