Modular techniques for noncommutative Gröbner bases

Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) (13P10) Software, source code, etc. for problems pertaining to associative rings and algebras (16-04) Gröbner-Shirshov bases (16Z10)

Abstract: In this note, we extend modular techniques for computing Gr"obner bases from the commutative setting to the vast class of noncommutative

G

-algebras. As in the commutative case, an effective verification test is only known to us in the graded case. In the general case, our algorithm is probabilistic in the sense that the resulting Gr"obner basis can only be expected to generate the given ideal, with high probability. We have implemented our algorithm in the computer algebra system {sc{Singular}} and give timings to compare its performance with that of other instances of Buchberger's algorithm, testing examples from

D

-module theory as well as classical benchmark examples. A particular feature of the modular algorithm is that it allows parallel runs.

Review text

Let \(K\) be a field and \(K\langle x\rangle\) the free associative \(K\)-algebra generated by \(x=(x_1,\ldots,x_n)\). A \(G\)-algebra over \(K\) is a factor algebra of type \[ A=K\langle x_1,\ldots,x_n\mid x_jx_i=c_{ij}x_ix_j+d_{ij}, 1\leq i<j\leq n\rangle \] where \(c_{ij}\in K\) and \(d_{ij}\) standard polynomials (i.e., polynomials with monomials of type \(x_1^{\alpha_1}\cdot\ldots\cdot x_n^{\alpha_n}\)) and the following hold: \begin{itemize} \item[(1)] There exists a monomial ordering \(>\) on \((x_1,\ldots,x_n)\) such that \(d_{ij}=0\) or \(x_ix_j> \text{leading monomial}(d_{ij}).\) \item[(2)] \(c_{ik}c_{jk}d_{ij}x_k-x_kd_{ij}+c_{jk}x_jd_{ik}-c_{ij}d_{ik}x_j+d_{jk}x_i-c_{ij}c_{ik}x_id_{jk}\) \end{itemize} reduce to zero with respect to the relations in \(A\). For \(G\)-algebras the theory of Gröbner bases is similar to the commutative case. There is an implementation to compute Gröbner bases for \(G\)-algebras in the computer algebra system Singular. If \(K=\mathbb Q\) it is known that there is often an intermediate coefficient swell during the computation. This can be avoided by using modular methods. This means to reduce the given ideal modulo several primes, compute a Gröbner basis for each reduced ideal and use Chinese remaindering and rational reconstruction to find the desired Gröbner basis over \(\mathbb Q\). The paper develops the theory (known in the commutative case) for \(G\)-algebras and describes the corresponding implementation in Singular.

Recommendations

Cites work

Cited in

(21)

Describes a project that uses

Uses Software

This page was built for publication: Modular techniques for noncommutative Gröbner bases

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2183734)