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.