Efficient Groebner bases computation over principal ideal rings

摘要

In this paper we present new techniques for improving the computation of strong Grobner bases over a principal ideal ring R. More precisely, we describe how to lift a strong Grobner basis along a canonical projection R - R, n not equal 0, and along a ring isomorphism R - R-1 x R-2. We then apply this to the computation of strong Grobner bases over a non-trivial quotient of a principal ideal domain RR. The idea is to run a standard Grobner basis algorithm pretending RR to be field. If we discover a non-invertible leading coefficient c, we use this information to try to split n = ab with coprime a, b. If this is possible, we recursively reduce the original computation to two strong Grobner bases computations over R/aR and R/bR respectively. If no such c is discovered, the returned Grobner basis is already a strong Grobner basis for the input ideal over RR. (C) 2019 Elsevier Ltd. All rights reserved.