Efficient algorithms and applications of symbolic computation

该计划的主要主题是设计、分析和实现符号计算(也称为计算机代数)中一些重要的非交换代数结构的有效算法，如Ore(斜)多项式、一些非交换环上的多项式、广义微分差分代数以及这些非交换代数上的矩阵。他们的研究是由编码理论、控制理论、密码学和工程等领域的许多应用推动的。*这一领域的挑战是，与交换情况相比，这些非交换代数通常具有更复杂的结构。尤其是，过去30年来符号计算中的许多算法突破并不明显地适用于非交换领域。这既是由于这些环中不存在特殊的数学性质，也是由于它们本身更难的公式。在这个项目下，我的研究将在理论和实践层面上考虑这些非交换代数中的一些最重要的计算问题，包括分解Ore多项式(包括单变量和多元情况)的快速算法，计算Ore多项式环上矩阵的标准形和逆的快速算法，以及计算广义微分-差分代数中Groebner基的快速算法，并希望实现对许多著名的非对易区域的统一和有效的方法。我们还希望给出一些应用，例如计算Gelfand-Kirillov维数，以及分类Post-Lie-Lie代数。这项建议的算法改进将在Maple、Sage和Single等计算机代数软件中实现。*建议的研究计划都涉及为他们未来在学术界和工业界的职位而广泛培训高素质人员(HQP)。*

The overarching theme of this proposed program is the design, analysis and implementation of efficient algorithms for a number of important non-commutative algebraic structures in symbolic computation (also called computer algebra), such as Ore (skew) polynomials, polynomials over some non-commutative rings, generalized differential-difference algebras and matrices over these non-commutative algebras. Their study is motivated by many applications in coding theory, control theory, cryptography and engineering, etc.******The challenge in this area is that these non-commutative algebras generally have a much more complex structure when compared with commutative case.  In particular, many of the algorithmic breakthroughs in symbolic computation over the past three decades do not obviously apply in non-commutative domains. This is due both to the non-existence of particular mathematical properties in these rings or their inherently more difficult formulations. My research under this program will be to consider some of the most important computational problems in these non-commutative algebras at both a theoretical and practical level, which include fast algorithms for factoring Ore polynomials (both simple variable and multivariate cases), computing normal forms and inverses of matrices over Ore polynomial rings, and fast algorithms for computing Groebner bases in generalized differential-difference algebra and hope to achieve a unified and efficient approach to many well-known non-commutative domains. We also wish to give some applications, e.g.,  computing Gelfand-Kirillov dimensions,  and classifying Post-Lie algebras. The algorithmic advances of this proposal will be implemented in computer algebra software such as Maple, SAGE and Singular.  ****The proposed research plans all involve extensive training of highly qualified personnel (HQP) for their future positions in academia and industry.********