Efficient Gröbner bases computation over principal ideal rings. (March 2021)

• Record Type: Journal Article
• Authors: Eder, Christian; Hofmann, Tommy
• Is Part Of: Journal of symbolic computation. Volume 103(2021)
• Page Start: 1
• Page End: 13
• Publication Date: 2021-03
• Subjects: Gröbner bases -- Principal ideal rings; 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.2019.10.020
• Languages: English
• ISSNs: 0747-7171

Abstract

Abstract: In this paper we present new techniques for improving the computation of strong Gröbner bases over a principal ideal ring R . More precisely, we describe how to lift a strong Gröbner basis along a canonical projection R → R / n, n ≠ 0, and along a ring isomorphism R → R 1 × R 2 . We then apply this to the computation of strong Gröbner bases over a non-trivial quotient of a principal ideal domain R / n R . The idea is to run a standard Gröbner basis algorithm pretending R / n R to be field. If we discover a non-invertible leading coefficient c, we use this information to try to split n = a b with coprime a, b . If this is possible, we recursively reduce the original computation to two strong Gröbner bases computations over R / a R and R / b R respectively. If no such c is discovered, the returned Gröbner basis is already a strong Gröbner basis for the input ideal over R / n R .