2014/04/05 by Yao Sun, Sun, Yao, Dongdai Lin +3 · 1 citation
Computer Science · Medicine · #Cancer Treatment and Pharmacology #Cryptography and Residue Arithmetic #FOS: Computer and information sciences #Polynomial and algebraic computation #Symbolic Computation (cs.SC) #cs.SC
paper · pdf · doi:10.48550/arxiv.1404.1428
openalex publication_date 2014/04/05 · arxiv created 2014/04/15 · arxiv updated 2014/04/16 · openalex created_date 2019/06/27 · openalex updated_date 2026/07/28
The GVW algorithm is a signature-based algorithm for computing Gröbner bases. If the input system is not homogeneous, some J-pairs with higher signatures but lower degrees are rejected by GVW's Syzygy Criterion, instead, GVW have to compute some J-pairs with lower signatures but higher degrees. Consequently, degrees of polynomials appearing during the computations may unnecessarily grow up higher and the computation become more expensive. In this paper, a variant of the GVW algorithm, called M-GVW, is proposed and mutant pairs are introduced to overcome inconveniences brought by inhomogeneous input polynomials. Some techniques from linear algebra are used to improve the efficiency. Both GVW and M-GVW have been implemented in C++ and tested by many examples from boolean polynomial rings. The timings show M-GVW usually performs much better than the original GVW algorithm when mutant pairs are found. Besides, M-GVW is also compared with intrinsic Gröbner bases functions on Maple, Singular and Magma. Due to the efficient routines from the M4RI library, the experimental results show that M-GVW is very efficient.