IngentaConnect Decomposing Monomial Representations of Solvable Groups

Author: Püschel M.

Source: Journal of Symbolic Computation, Volume 34, Number 6, December 2002 , pp. 561-596(36)

Abstract:

We present an efficient algorithm that decomposes a monomial representation of a solvable groupG into its irreducible components. In contradistinction to other approaches, we also compute the decomposition matrixA 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 forG. 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. Copyright 2002 Elsevier Science Ltd. All rights reserved.

Language: English

Document Type: Research article

DOI: 10.1006/jsco.2002.0566

Affiliations: Department of Electrical and Computer Engineering, Carnegie Mellon University, 5000 Forbes Avenue, PA 15213, Pittsburgh, U.S.A.:

The full text electronic article is available for purchase. You will be able to download the full text electronic article after payment.

$59.66 plus tax