About

AREP is a GAP (v3.4.4) share package which provides an infrastructure and high level functions to do symbolic computation in constructive representation theory. By the term "constructive" we mean that group representations are constructed and manipulated up to equality - not only up to equivalence as it is done by using characters. Hence you can think of it as working with matrix representations, but in an efficient way using the special structure of the matrices occuring in representation theory of finite groups.

A striking application of constructive representation theory is the decomposition of matrices representing discrete signal transforms into a product of highly structured sparse matrices (Examples). This decomposition represents a fast algorithm for the signal transform. Another application is the construction of fast Fourier transforms for solvable groups. The package has evolved out of this area of application into a more general tool.

As said above, AREP can generate, entirely automatically, fast algorithms for many different signal transforms. This is remarkable, since 1) these algorithms are usually hand derived and then published in journals, and 2) tha fact that this is possible shows a strong relationship between signal processing and algebra. The SMART project explores and extends this connection.

AREP stands for Abstract REPresentations. We have chosen "abstract" because we manipulate expressions for representations, not constants. However, "concrete" would also be right because the representations are given with respect to a fixed basis of the underlying vector space. The name AREP is thus, for historical reasons, somewhat misleading.

The package was originally developed at the IAKS, University Karlsruhe by Sebastian Egner and Markus Püschel.

Functionality

The package AREP provides the following functionality:

  • Efficient representation and computation with monomial matrices
  • Symbolic computation with group representations and structured matrices
  • Special attention on representing and manipulating monomial representations
  • Symmetry analysis of matrices
  • Decomposition of arbitrary monomial representations of solvable groups
  • Derivation of fast Fourier transforms for solvable groups
  • Automatic derivation of fast discrete signal transforms (Example: DCT)

Package and Manual

The last released version is 1.2 and can be obtained as gzipped tar-file (1.23 MB). To install the package you need GAP v3.4.4. Some functions in AREP require the first 9 bugfixes to be applied. The version 1.0 can be obtained on the GAP server. You can also download the manual (arep_manual.ps.gz, 164 KB) seperately. Since GAP 3 is not supported anymore by the GAP group, AREP is now maintained as part of SPIRAL. If you download and install SPIRAL, AREP is automatically included.

More Information

Large parts of AREP are based on the two papers Symmetry-Based Matrix Factorization and Decomposing Monomial Representations of Solvable Groups.

AREP and SPIRAL

The algorithms for discrete signal transforms as found by AREP can be directly translated into efficient C/Fortran code using SPL and the SPL compiler, which have been developed in the SPIRAL project. This automates the entire process of finding a fast algorithm for a given signal transform. See how this procedure works for an 8 x 8 DCT (discrete cosine transform).