A factorization algorithm for G-algebras and its applications. (March 2018)

• Record Type: Journal Article
• Authors: Levandovskyy, Viktor; Heinle, Albert
• Is Part Of: Journal of symbolic computation. Volume 85(2018)
• Page Start: 188
• Page End: 205
• Publication Date: 2018-03
• Subjects: G-algebra -- PBW algebra -- Algebra of solvable type -- Gröbner basis -- Factorization -- Noncommutative Gröbner basis -- Noncommutative factorization -- Factorizing Gröbner basis -- Factorized Gröbner basis; Mathematics -- Data processing -- Periodicals; Numerical analysis -- Data processing -- Periodicals; Automatic programming (Computer science) -- Periodicals; Mathématiques -- Informatique -- Périodiques; Analyse numérique -- Informatique -- Périodiques; Programmation automatique -- Périodiques; Automatic programming (Computer science); Mathematics -- Data processing; Numerical analysis -- Data processing; Periodicals; Electronic journals; 510.285
• DOI: 10.1016/j.jsc.2017.06.005
• Languages: English
• ISSNs: 0747-7171

Abstract

Abstract: 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 Gröbner 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.