“School of Mathematics”

Back to Papers Home
Back to Papers of School of Mathematics

Paper   IPM / M / 17759
School of Mathematics
  Title:   Improvement of an incremental signature-based comprehensive Grobner system algorithm
  Author(s):  Mahdi Dehghani Darmian
  Status:   Published
  Journal: Math. Comput. Sci.
  Vol.:  18
  Year:  2024
  Pages:   11-25
  Supported by:  IPM
In this paper, we improve the GVWDisPGB algorithm for computing comprehensive Grobner systems developed by Hashemi et al. in [19]. The GVWDisPGB algorithm is equipped with an incremental structure using the GVW algorithm [13], which takes advantage of the F5 criteria [9] to remove superfluous reductions. While constructing the Grobner basis of a given ideal in the polynomial ring of variables, this algorithm creates new branches in the parameters space to cover all possible parameter values. To improve this algorithm, we use parametric linear algebra techniques for the initial (not complete) partitioning of parameters space. More precisely, we install a minor modified GES algorithm [6] on the GVWDisPGB algorithm to compute a Gaussian elimination system of parametric matrices (corresponding parametric linear ideal). We show that there exist many examples such that our algorithm, the so-called GES-GVW-CGS algorithm is faster than the GVWDisPGB algorithm because of constructing fewer branches and consequently having less complexity. All mentioned algorithms have been implemented in Maple, and their efficiency has been experimented on a diverse set of benchmark polynomials.

Download TeX format
back to top
scroll left or right