Decomposing monomial representations of solvable groups. We present an efficient algorithm that 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 provides 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 concrete matrix representations are considered and manipulated, rather than equivalence classes of representations as it is done in approaches that are based on characters. Thus, we present well-known theorems in a constructively refined form and derive new results on decomposition matrices of representations. Our decomposition algorithm has been implemented in the GAP share package AREP. One application of the algorithm is the automatic generation of fast algorithms for discrete linear signal transforms.
Keywords for this software
References in zbMATH (referenced in 9 articles , 1 standard article )
Showing results 1 to 9 of 9.
- Püschel, Markus; Rötteler, Martin: Algebraic signal processing theory: Cooley-Tukey type algorithms on the 2-D hexagonal spatial lattice (2008)
- Rötteler, Martin: Quantum algorithms: a survey of some recent results (2006) ioport
- Clausen, M.; Müller, M.: Generating fast Fourier transforms of solvable groups (2004)
- Egner, Sebastian; Püschel, Markus: Symmetry-based matrix factorization (2004)
- Püschel, Markus; Moura, José M. F.: The algebraic approach to the discrete cosine and sine transforms and their fast algorithms (2003)
- Püschel, Markus: Decomposing monomial representations of solvable groups. (2002)
- Egner, Sebastian; Johnson, Jeremy; Padua, David; Püschel, Markus; Xiong, Jianxin: Automatic derivation and implementation of signal processing algorithms (2001)
- Püschel, Markus; Singer, Bryan; Veloso, Manuela; Moura, José M.F.: Fast automatic generation of DSP algorithms (2001)
- Püschel, Markus; Rötteler, Martin; Beth, Thomas: Fast quantum Fourier transforms for a class of non-abelian groups (1999)