Development, implementation and applications of fundamental algorithms, relying on Gröbner bases in free associative algebras

依赖于自由联想代数中的 Gröbner 基础的基础算法的开发、实现和应用

• 批准号: 171336129
• 负责人: Professor Dr. Martin Kreuzer
• 金额: --
• 依托单位: Lehrstuhl für Mathemathik mit Schwerpunkt Symbolic Computation
• 依托单位国家: 德国
• 项目类别: Priority Programmes
• 财政年份: 2010
• 资助国家: 德国
• 起止时间: 2009-12-31 至 2014-12-31
• 项目状态: 已结题
• 来源: https://gepris.dfg.de/gepris/projekt/171336129?language=en
• 关键词: Development; implementation; applications; fundamental; algorithms

This project is part of mathematical Computer Algebra. It has applications in Ring Theory, Representation Theory, Computer Science and other disciplines. In order to perform Gröbner basis-like computations in a free associative algebra, one can use the recently developed letterplace correspondence between ideals and perform the computations in a large commutative polynomial ring. Such rings have been intensively studied before, in particular from a computer algebraic point of view. As a result, very effective data structures are known and fundamental algorithms have been optimized and implemented in computer algebra systems. The corresponding situation for non-commutative rings is less developed. The systematic use of the letterplace correspondence provides new insights and new levels of efficiency into the challenging realm of computations in free algebras and their factor rings. We aim at the creation of an extension LETTERPLACE of the well-known computer algebra system SINGULAR. This will for the first time provide efficient implementations of Gröbner bases and all the basic algorithms involving Gröbner bases in these algebras, for instance syzygy modules, elimination, kernels of ring and module homomorphisms. A preliminary implementation of the Letterplace Gröbner basis algorithm is available in the kernel of SINGULAR and it has already demonstrated very good performance. The next step will be to use these implementations to tackle hitherto unaccessible problems. For instance, we intend compute the K-dimension, explicit K-bases and (truncated) Hilbert series for non-commutative K-algebras. Another area of applications are computations in monoid and group rings where we plan to adress questions such as finiteness of a finitely presented group, the generalized word problem, the conjugator search problem, freeness tests for groups and the structure of the group of torsion elements of a group algebra. To guide these applications, we intend to collaborate with several research groups in Germany and across the world.

这个项目是数学计算机代数的一部分。它在环论、表示论、计算机科学等学科中有应用。为了在自由结合代数中进行类似Gröbner基的计算，可以使用最近发展的理想之间的字母位置对应，并在一个大的交换多项式环中进行计算。这样的环已经深入研究之前，特别是从计算机代数的角度来看。因此，非常有效的数据结构是已知的，基本的算法已被优化，并在计算机代数系统中实现。非交换环的相应情况较少发展。系统地使用字母对应提供了新的见解和新的效率水平到具有挑战性的领域的计算自由代数及其因子环。我们的目标是创建一个扩展的LETTERPLACE的著名的计算机代数系统奇异。这将是第一次提供有效的实现Gröbner基地和所有的基本算法涉及Gröbner基地在这些代数，例如syzygy模块，消除，内核的环和模块同态。在SINGULAR的内核中可以初步实现Letterplace Gröbner基算法，并且已经表现出非常好的性能。下一步将是使用这些实现来解决迄今为止无法解决的问题。例如，我们打算计算非交换K-代数的K-维，显式K-基和（截断）Hilbert级数。另一个领域的应用是计算在幺半群和群环，我们计划解决的问题，如有限性的一个群，广义字的问题，共轭搜索问题，自由度测试的群体和结构的一组扭转元素的一组代数。为了指导这些应用，我们打算与德国和世界各地的几个研究小组合作。