×

An algorithm to calculate the kernel of certain polynomial ring homomorphisms. (English) Zbl 0860.68062

The Buchberger algorithm can calculate a finite basis for the kernel of a ring homomorphism \(\pi:K_x\to K_y\) applying it over a polynomial the ring \(K_{x,y}\). Nevertheless, the algorithm complexity grows very fast with the increase in the number of variables. In this paper, the authors propose an alternative algorithm to compute the kernel of a polynomial map assuming that the map takes monomials into monomials. The starting point for the alternative algorithm was that in some situations it seems more reasonable to compute the Gröbner basis over \(K_x\) instead of over \(K_{x,y}\), as over the former there is a larger number of variables.
The paper presents a brief review of Gröbner basis computation over \(K_{x,y}\), illustrating with examples. Following that, the solution proposed is fully discussed. The algorithm to compute the kernel of \(\pi\) is summarized and a couple of examples are given to show how it works. The complexity of the algorithm is studied and it is shown that it requires the determination of at most \(\lfloor{1\over 2}n\rfloor\) Gröbner basis over \(K_x\), whereas the Buchberger algorithm has a higher complexity as it computes the Gröbner basis over \(K_{x,y}\), which has more variables. The performance of the algorithm was investigated taking 500 random examples on a NeXT computer with 25 MHz and 20 Mb of RAM, making use of the Mathematica and PARI computer algebra systems. The results indicate that the proposed algorithm has a significant decrease in running time and additionally requires much less memory. The performance results are displayed in a table for both methods. The method proposed is useful, but as the authors comment it is limited as it can only be applied to a map \(\pi\) that sends monomials into monomials.

MSC:

68W30 Symbolic computation and algebraic computation
13P10 Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases)
68Q25 Analysis of algorithms and problem complexity
PDF BibTeX XML Cite
Full Text: DOI Euclid EuDML EMIS

References:

[1] Adams W. W., An Introduction to Gröbner Bases (1994) · Zbl 0803.13015
[2] Batut C., User’s Guide to Pari-GP.
[3] Bayer D., Macaulay: A Computer Algebra System for Algebraic Geometry.
[4] Buchberger B., Multidimensional Systems Theory (1985) · Zbl 0587.13009
[5] Cohen H., A Course in Computational Algebraic Number Theory (1993) · Zbl 0786.11071
[6] DOI: 10.1007/3-540-54522-0_102
[7] Cox D., Ideals, Varieties, and Algorithms (1991)
[8] Diaconis P., ”Algebraic algorithms for sampling from conditional distributions” · Zbl 0952.62088
[9] DOI: 10.1007/BF01273309 · Zbl 0211.33801
[10] Hosten S., ”GRIN: An implementation of Gröbner bases for integer programming” (1994)
[11] DOI: 10.1007/BF01386834 · Zbl 0785.13009
[12] Natraj N. R., ”An algebraic geometry algorithm for scheduling in the presence of setups and correlated demands” · Zbl 0839.90063
[13] Thomas R. R., ”A geometric Buchberger algorithm for integer programming” · Zbl 0846.90079
[14] Wolfram S., Mathematica: A System for Doing Mathematics by Computer,, 2. ed. (1991) · Zbl 0671.65002
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.