Automatic Generation of Transform Algorithms
Using methods from representation theory of groups and algebras, it is possible to automatically generate fast algorithms for discrete signal transforms straight from their definition using a computer program. Have a look at the following examples:
The fact that this is possible spawned the SMART project to understand the connection between algebra and signal processing.
More recently we have applied AREP to generate fast algorithms for matrices arising in finite element computations.
Robert Kirby and Markus Püschel
Program Generation for Polynomial Transforms in Unstructured Finite Element Computation
Proc. Finite Element Methods in Engineering and Science (FEMTEC) 2006
Efficient algorithms for applying operators lie at the heart of spectral element methods. Though algorithms are known, spectral methods are much more complicated on unstructured elements than on structured meshes. The critical issue is finding a combination of an expansion basis and a quadrature rule for which a function can be efficiently evaluated and differentiated at the quadrature points. Rather than looking for an explicit tensor product structure as in or using dense matrix operations as in, we view the evaluation as a polynomial transform. In the SMART project it was shown that fast Fourier transform like algorithms for a large class of such transforms can be generated automatically using algebraic techniques from representation theory using a tool called AREP. The output of AREP can then be fed into SPIRAL to obtain an actual optimized C implementation. We study the application of AREP and SPIRAL to automatically generate optimized black-box code for evaluating standard finite element bases. Experiments show that, for example, for evaluating derivatives of the third degree Lagrange basis functions at suitably chosen quadrature points, AREP and SPIRAL can reduce the operations count and the runtime by a factor of 2-4. These results suggest that it is possible to obtain reliable, elegant, high-performance finite element algorithms with a minimum of human involvement.
Sebastian Egner and Markus Püschel
Symmetry-Based Matrix Factorization
Journal of Symbolic Computation 2004, Special Issue on Computer Algebra and Signal Processing, Vol. 37, No. 2, pp. 157-186
An algebraic method is presented to construct a fast algorithm for a given discrete linear signal transforms which contains a sufficiently strong "symmetry" (in a sense being defined). The transform is given in the form of a defining matrix. The algorithm is a factorization of this matrix into a short product of sparse matrices such as permutation matrices and diagonal matrices. The approach extends the well known concept of discrete Fourier transforms over finite groups and became feasible through two advances: A method to decompose monomial representations of solvable groups by structural recursion and a method to compute certain symmetries of matrices by combinatorial search. The methods have been implemented in the library AREP and used to generate fast algorithms for a class of transforms including the discrete Fourier, cosine, sine, and Hartley transform, automatically.<\p>
algogen.ps (396 KB)
- Markus Püschel
Decomposing Monomial Representations of Solvable Groups
Journal of Symbolic Computation 2002, Vol. 34, No. 6, pp. 561-596
We present an efficient algorithm which decomposes a monomial representation of a solvable group G into its irreducible components. In contradistinction to other approaches we also compute the decomposition matrix A in the form of a product of highly structured, sparse matrices. This factorization can be viewed as a fast algorithm for the multiplication with A. In the special case of a regular representation we hence obtain a fast Fourier transform for G. Our algorithm is based on a constructive representation theory that we develop. The term "constructive" signifies that representations are considered and manipulated up to equality and not only up to equivalence as it is done in approaches that are based on characters. Thus, we present some well-known theorems in a constructively refined form and derive some new results on decomposition matrices. All results in this paper have been implemented in the GAP share package AREP.
mondec.ps (686 KB)
- Sebastian Egner and Markus Püschel
Automatic Generation of Fast Discrete Signal Transforms
IEEE Trans. on Signal Processing 2001, Vol. 49, No. 9, pp. 1992-2002
This paper presents an algorithm that derives fast versions for a broad class of discrete signal transforms symbolically. The class includes but is not limited to the discrete Fourier and the discrete trigonometric transforms. This is achieved by finding fast sparse matrix factorizations for the matrix representations of these transforms. Unlike previous methods, the algorithm is entirely automatic and uses the defining matrix as its sole input. The sparse matrix factorization algorithm consists of two steps: first, the "symmetry" of the matrix is computed in the form of a pair of group representations; second, the representations are stepwise decomposed, giving rise to a sparse factorization of the original transform matrix. We have successfully demonstrated the method by computing automatically efficient transforms in several important cases: for the DFT, we obtain the Cooley/Tukey FFT; for a class of transforms including the DCT, type 2, the number of arithmetic operations for our fast transforms is the same as for the best known algorithms. Our approach provides new insights and interpretations for the structure of the considered signal transforms and why fast algorithms do exist. The sparse matrix factorization algorithm is implemented within the software package AREP.
autgen.pdf (256 KB)
- Sebastian Egner, Jeremy Johnson, David Padua, Markus Püschel, and Jianxin Xiong
Automatic Derivation and Implementation of Signal Processing Algorithms
ACM SIGSAM Bulletin Communications in Computer Algebra 2001, Vol. 35, No. 2, pp. 1-19
We present a computer algebra framework to automatically derive and implement algorithms for digital signal processing. The two main parts of the framework are AREP, a library for symbolic manipulation of group representations and structured matrices, and SPL, a compiler turning matrix expressions into efficient imperative-style numerical programs. Example: DCT
areptpl.pdf (256 KB)