Copyrights to these papers may be held by the publishers. The download files are preprints. It is understood that all persons copying this information will adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.
Sebastian Egner and Markus Püschel (Journal of Symbolic Computation, special issue on "Computer Algebra and Signal Processing", Vol. 37, No. 2, pp. 157-186, 2004)
Symmetry-Based Matrix Factorization
Preprint (330 KB)
Bibtex
We present a method to factor a given matrix M into a short product of sparse matrices, provided M has a suitable ``symmetry''. This sparse factorization represents a fast algorithm for the matrix-vector multiplication with M. The factorization method consists of two essential steps. First, a combinatorial search is used to compute a suitable symmetry of M in the form of a pair of group representations. Second, the group representations are decomposed stepwise, which yields factorized decomposition matrices and determines a sparse factorization of M. The focus of this article is the first step, finding the symmetries. All algorithms described have been implemented in the library AREP. We present examples for automatically generated sparse factorizations---and hence fast algorithms---for a class of matrices corresponding to digital signal processing transforms including the discrete Fourier, cosine, Hartley, and Haar transform.
Keywords: Theory of transform algorithms, AREP: Software for algorithm discovery, Group representation theoryMore information: