Fast Management of Permutation Groups I
Fast Management of Permutation Groups I
复制标题
排列群的快速管理 I
DOI：
--
复制
发表时间：
1997
期刊：
影响因子：
--
通讯作者：
Á. Seress
中科院分区：
文献类型：
--
作者：
L. Babai;E. Luks;Á. Seress
提出了一种新的置换群处理算法。我们的方法在寻找强发电机组和检验隶属度等基本问题的最坏情况分析方面取得了近一个数量级的改进。即使在这样的基本问题上，团体的正常结构也会发挥作用。一个基本要素是识别给定组的大交替组成因子，并随后扩展排列域以显示这些交替组的自然作用。进一步的新特性包括对交替组的新颖快速处理和对定义关系的筛选，以便将这些和其他分析因素与组的其余部分联系起来。该算法的分析依赖于有限简单群的分类。在本文的后续文章中，我们将利用对现有方法的改进，实现进一步的数量级改进。
We present new algorithms for permutation group manipulation. Our methods result in an improvement of nearly an order of magnitude in the worst-case analysis for the fundamental problems of finding strong generating sets and testing membership. The normal structure of the group is brought into play even for such elementary issues. An essential element is the recognition of large alternating composition factors of the given group and subsequent extension of the permutation domain to display the natural action of these alternating groups. Further new features include a novel fast handling of alternating groups and the sifting of defining relations in order to link these and other analyzed factors with the rest of the group. The analysis of the algorithm depends on the classification of finite simple groups. In a sequel to this paper, using an enhancement of the present method, we shall achieve a further order of magnitude improvement.