Factorization of ℤ $$ \mathbb {Z}$$ -Homogeneous Polynomials in the First q-Weyl Algebra

Factorization of elements of noncommutative rings is an important problem both in theory and applications. For the class of domains admitting nontrivial grading, we have recently proposed an approach, which utilizes the grading in order to factor general elements. This is heavily based on the factorization of graded elements. In this paper, we present algorithms to factorize weighted homogeneous (graded) elements in the polynomial first q-Weyl and Weyl algebras, which are both viewed as ℤ $${ \mathbb {Z}}$$ -graded rings. We show that graded polynomials have finite number of factorizations. Moreover, the factorization of such can be almost completely reduced to commutative univariate factorization over the same base field with some additional uncomplicated combinatorial steps. This allows to deduce the complexity of our algorithms in detail, which we prove to be polynomial-time. Furthermore, we show, that for a graded polynomial p, irreducibility of p in the polynomial first Weyl algebra implies its irreducibility in the localized (rational) Weyl algebra, which is not true for general polynomials. We report on our implementation in the computer algebra system Singular. For graded polynomials, it outperforms currently available implementations for factoring in the first Weyl algebra—in speed as well as in elegancy of the results.