Efficient Computation in Finite Groups

有限群中的高效计算

• 批准号: 0514122
• 负责人: Akos Seress
• 金额: --
• 依托单位: Ohio State University Research Foundation -DO NOT USE
• 依托单位国家: 美国
• 项目类别: Continuing grant
• 财政年份: 2005
• 资助国家: 美国
• 起止时间: 2005-06-01 至 2008-05-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0514122&HistoricalAwards=false
• 关键词: Efficient; Computation; Finite; Groups

Group theory is the mathematical theory of symmetry. Algorithms for finite groups and their associated graphs have a wide range of applications in mathematics, the physical sciences, and computer science. This project has two main foci. The first one is the development of a unified data structure for the algorithmic treatment of finite groups in their concrete representations as permutation groups or matrix groups; the second one is the design, analysis, and implementation of algorithms for large dimensional matrix groups, applying the unified framework. Implementations of the new algorithms will be distributed worldwide in the GAP computer algebra system and they will contribute to a computational environment in GAP for research in group theory, algebra, graph theory, coding theory, and design theory, and to computer-based educational materials for undergraduate algebra courses.The project will develop divide-and-conquer techniques for various classes of Aschbacher's classification of matrix groups, thereby reducing the computations to smaller dimensional matrix groups or to permutation groups. Also, particular emphasis is placed on algorithms dealing with simple groups, which are the final stages of recursion in this divide-and-conquer scheme. The research also includes problems in group theory and combinatorics which are either necessary for the proof of correctness of the algorithms, or became accessible by the new machinery. In particular, these problems include the minimum base size and minimal suborbit size of primitive permutation groups, diameter estimates of Cayley graphs of almost simple groups, finding short presentations for simple groups, and the construction of highly symmetric graphs with a distinguished set of cycles.

群论是对称的数学理论。有限群及其相关图的算法在数学、物理科学和计算机科学中有着广泛的应用。这个项目有两个重点。第一个是开发一种统一的数据结构，用于算法处理作为置换群或矩阵群的具体表示的有限群；二是采用统一的框架，设计、分析和实现大维矩阵群的算法。新算法的实现将在GAP计算机代数系统中分布全球，它们将为GAP研究群论、代数、图论、编码理论和设计理论提供计算环境，并为本科代数课程提供基于计算机的教育材料。该项目将开发针对不同类别的Aschbacher矩阵群分类的分治技术，从而将计算减少到更小维度的矩阵群或置换群。此外，还特别强调了处理简单组的算法，这是分治方案中递归的最后阶段。研究还包括群论和组合学中的问题，这些问题要么是证明算法正确性所必需的，要么是新机器可以访问的。特别是，这些问题包括原始置换群的最小基大小和最小子轨道大小，几乎简单群的Cayley图的直径估计，寻找简单群的简短表示，以及具有不同循环集的高度对称图的构造。