Signature-based standard basis algorithm under the framework of GVW algorithm (Dingkang Wang and collaborators)

The GVW algorithm, one of the most important so-called signaturebased algorithms, is designed to eliminate a large number of useless polynomial reductions from Buchberger's algorithm. The cover theorem serves as the theoretical foundation of the GVW algorithm, and up to now, it applies only to a certain class of monomial orders, namely global orders and a special class of local orders. In this paper we extend this theorem to any semigroup order, which can be either global, local or even mixed. Building upon the pioneering idea of the Mora normal form algorithm, we propose a more comprehensive and general proof for the cover theorem while bypassing the need to choose a minimal element from an infinite set of monomials in all the existing proofs. Therefore, the algorithm for signature-based standard bases is presented for any semigroup order under the framework of the GVW algorithm, and an example is given to provide an illustration of the algorithm. (c) 2024 Elsevier Ltd. All rights are reserved, including those for text and data mining, AI training, and similar technologies.

Publication:

Journal of Symbolic Computation Volume 127, March–April 2025

https://doi.org/10.1016/j.jsc.2024.102370

Author:

Dong Lu

School of Mathematics, Southwest Jiaotong University, Chengdu 610031, China

Email: donglu@swjtu.edu.cn

Dingkang Wang

KLMM, Academy of Mathematics and Systems Science, CAS, Beijing 100190, China

School of Mathematical Sciences, University of Chinese Academy of Sciences, Beijing 100049, China

Email: dwang@mmrc.iss.ac.cn

Fanghui Xiao

MOE-LCSM, School of Mathematics and Statistics, Hunan Normal University, Changsha 410081, China

Email: xiaofanghui@hunnu.edu.cn

Xiaopeng Zheng

College of Mathematics and Computer Science, Shantou University, Shantou 515821, China

Email: zhengxiaopeng@amss.ac.cn