The Atlas of Finite Groups - Ten Years on: The Meataxe as a tool in computational group theory
The Atlas of Finite Groups - Ten Years on: The Meataxe as a tool in computational group theory
复制标题
有限群图集 - 十年过去了：Meataxe 作为计算群论的工具
DOI：
10.1017/cbo9780511565830.011
复制
发表时间：
1998
影响因子：
1.8
通讯作者：
D. Holt
中科院分区：
文献类型：
--
作者：
D. Holt
Meataxe算法是由Richard帕克首先提出的一个实用算法，用于检验有限域上有限维模的不可约性，以及在可约情况下寻找显式子模。这和相关的算法进行了简要描述，连同最近的改进。本文还讨论了将这些方法推广到有理数等特征为零的领域的可能性。明确地找到有限维KG -模的不可约成分的问题，其中K是域，G是有限群，毫无疑问是计算群表示论中最基本的问题。它大致相当于找到一个有限置换群的轨道，除了它是相当困难。迄今为止，对这个问题的大多数研究都局限于K = GF（q）是有限的情况，我们将在本文的前两节中假设这是真的。特征零的情况将在第3节讨论。我们将自始至终用d来表示表示的次数。Ronyai在[12]中证明了该问题的理论复杂度是d log（q）的多项式，但那里描述的算法似乎并不实用，并且复杂度至少与O（d 6 log（q））一样糟糕。对于当前的应用程序，它是必不可少的，以找到方法，是实际的d等于至少几千，为了实现这一点，我们必须以复杂度O（d 3 log（q））。在实践中，这等于两个矩阵相乘、矩阵求逆或执行高斯约简的复杂性。
Abstract The Meataxe is a practical algorithm, first introduced by Richard Parker, for testing finite dimensional modules over finite fields for irreducibility, and for finding explicit submodules in the reducible case. This and associated algorithms are described briefly, together with more recent improvements. The possibility of extending these methods to fields of characteristic zero, such as the rational numbers, is also discussed. Chopping up modules The problem of explicitly finding the irreducible constituents of a finite dimensional KG -module, where K is a field and G is a finite group, is without doubt the most basic problem in computational group-representation theory. It corresponds roughly to finding the orbits of a finite permutation group, except that it is considerably more difficult. Most of the research on this problem to date has been restricted to the case where K = GF ( q ) is finite, and we shall assume this to be true in the first two sections of this paper. The characteristic zero case will be discussed in section 3. We shall denote the degree of the representation by d , throughout. The theoretical complexity of the problem was proved to be polynomial in d log( q ) by Ronyai in [12], but the algorithm described there does not appear to be practical as it stands, and has complexity at least as bad as O ( d 6 log( q )). For current applications, it is essential to find methods that are practical for d equal to at least several thousand and, to achieve this, we must aim for complexity O ( d 3 log( q )). In practice, this is equal to the complexity of multiplying two matrices, inverting a matrix, or performing a Gaussian reduction.