Applications of Group Theory to Large Scale Computation

该项目解决了目前超出当前算法和现有技术范围的有限群的计算问题。群被表示为置换群或定义在有限域上的矩阵群。这些问题既关系到群论的结构，也关系到群论的应用。本研究的中心动机是构造有限域上定义的矩阵群的表示。这是大规模国际努力开发一套执行矩阵群计算的计算工具的重要组成部分。要开发的工具可以应用于物理科学、工程和那些处理高维矩阵表示群的数学部分的问题。第二个研究领域是求解有限群最小字问题的计算技术。这个问题出现在许多情况下，例如互连网络中的路由和编码理论，并且已知是计算困难的。这项研究将产生新的算法，利用群自同构来修剪可能解的搜索树。第三个研究领域是开发一种软件体系结构，使并行计算机能够处理计算群理论中的大规模问题，例如超大矩阵和置换表示的构造。如集成的、交互的环境将使研究人员能够迅速克服最初的学习障碍，有效地利用并行性。他们将能够在他们的家庭站点（例如学生实验室）将现成的工作站网络与已经熟悉的语言（例如GAP或LISP）结合起来。

This project addresses computational issues for finite groups that are currently beyond the scope of current algorithms and existing technology. The groups are represented either as permutation groups or as matrix groups defined over finite fields. The questions of interest concern both group theoretic structure and applications of the group theory. A central motivation for the research is the construction of representations for matrix groups defined over finite fields. This is an important part of a large-scale international effort to develop a suite of computational tools for performing matrix group computations. The tools to be developed have application to problems in the physical sciences, engineering, and those parts of mathematics dealing with high dimensional matrix representations of groups. A second research area computational techniques for solving the minimum word problem for finite groups. This problem arises in many contexts, such as routing in interconnection networks and coding theory, and is known to be computationally difficult. The research will lead to new algorithms which use group automorphisms to prune the search tree of possible solutions. A third research area is the development of a software architecture to bring parallel computers to bear on large scale problems in computational group theory, such as the construction of very large matrix and permutation representations. Such as integrated, interactive environment will enable researchers to quickly overcome the initial learning barrier for effective use of parallelism. They will be able to combine readily available networks of workstations at their home site (such as student labs), with an already familiar language, such as GAP or LISP.