Modular Techniques for Noncommutative Gröbner Bases

We extend modular techniques for computing Gröbner 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 t...

Full description

Saved in:
Bibliographic Details
Published in:Mathematics in computer science 2020-03, Vol.14 (1), p.19-33
Main Authors: Decker, Wolfram, Eder, Christian, Levandovskyy, Viktor, Tiwari, Sharwan K.
Format: Article
Language:English
Subjects:
Algorithms
Computer algebra
Computer Science
Mathematics
Mathematics and Statistics
Statistical analysis
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We extend modular techniques for computing Gröbner 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öbner basis can only be expected to generate the given ideal, with high probability. We have implemented our algorithm in the computer algebra system 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.
ISSN:1661-8270
1661-8289
DOI:10.1007/s11786-019-00412-9