An Algorithm for Computing Minimal Associated Primes of Binomial Ideals without Producing Redundant Components
Toru Aoyama · 2017
This paper proposes a new algorithm for computing the minimal associated primes of a binomial ideal in a polynomial ring over a field. We utilize the cellular decomposition as an intermediate decomposition. It is defined by Eisenbud-Sturmfels and improved by Kahle. In addition, following some parts of the algorithm by Laplagne, a new algorithm for an intermediate decomposition is constructed. Our algorithm decomposes an ideal into cellular ideals whose sets of minimal associated primes are disjoint. It needs neither extensions of the coefficient field nor reductions to the zero-dimensional case. Most of the computations are saturations. We observe by this intermediate decomposition, binomial ideals are decomposed into components whose radicals correspond to the minimal associated primes in many cases. This algorithm executes nilpotency checks, radical membership tests and computations of saturations many times. Therefore, we try to speed up the check of I = I : f (f is a polynomial) which is necessary for above computations. As a result, we obtain efficient algorithms including heuristic and optional methods.