A factorization algorithm for G-algebras and its applications

作者：Levandovskyy Viktor^*; Heinle Albert

来源：Journal of Symbolic Computation, 2018, 85: 188-205.

DOI：10.1016/j.jsc.2017.06.005

• G-algebra
• PBW algebra
• Algebra of solvable type
• Grobner basis
• Factorization
• Noncommutative Grobner basis
• Noncommutative factorization
• Factorizing Grobner basis
• Factorized Grobner basis

Factorization of polynomials into irreducible factors is an important problem with numerous applications, both over commutative and over non-commutative rings. It has been recently proved by Bell, Heinle and Levandovskyy that a large class of non-commutative algebras are finite factorization domains (FFD for short). This provides a termination criterion for a factorization algorithms of elements in a vast class of finitely presented K-algebras, which includes the ubiquitous G-algebras, encompassing algebras of common linear partial functional operators.
In this paper, we contribute an algorithm to find all distinct factorizations of a given element in a G-algebra, with minor assumptions on the underlying field, and establish its complexity. Moreover, the property of being an FFD, in combination with the factorization algorithm, enables us to generalize the factorizing Grobner basis algorithm for G-algebras. This algorithm is useful for various applications, e.g. in analysis of solution spaces of systems of linear partial functional equations with polynomial coefficients. Additionally, it is possible to include inequality constraints for ideals in the input.
The developed algorithms are accompanied by freely available implementations and illustrated by interesting examples.

• 出版日期2018-4