An efficient method for computing comprehensive Gröbner bases

DOI10.1016/J.JSC.2012.05.015MaRDI QIDQ1940934zbMATH OpenOpenAlexFDO

Authors Deepak Kapur, Yao Sun, Dingkang Wang

Publication date 11 March 2013

Published in Journal of Symbolic Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jsc.2012.05.015

zbMATH Keywords

comprehensive Gröbner basis comprehensive Gröbner system Gröbner basis stability condition

Mathematics Subject Classification ID

Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) (13P10)

Review text

The concept of a comprehensive Gröbner basis was introduced by \textit{V. Weispfenning} [J. Symb. Comput. 36, No. 3-4, 669--683 (2003; Zbl 1054.13015)] as a special basis of a parametric polynomial system such that for every possible specialization of its parameters, the basis obtained from the comprehensive Gröbner basis serves as a Gröbner basis of the ideal generated by the specialization of the parametric polynomial system. In the paper under review, the authors present an efficient method to keep track of faithful polynomials during the computations, such that a comprehensive Gröbner basis of a parametric polynomial system can be constructed more efficiently. The key idea is to split a polynomial into two parts -nonzero part and zero part for the specialization under consideration. The proposed idea can be used in all algorithms for computing comprenhensive Gröbner systems. The main result of the paper (Theorem 4.6) gives a direct way to compute a comprehensive Gröbner system and a comprehensive Gröbner basis simultaneously and the correctness of the new algorithm is a direct consequence of this result. The core of the new algorithm is an efficient algorithm for computing a comprehensive Gröbner system proposed by the authors [``A new algorithm for computing comprehensive Gröbner systems. in: Proc. ISSAC 2010, 29--36 (2010)]. The authors have done a detailed comparative analysis and experiments that show that the algorithm is faster in practice than known existing algorithms primarily. The authors point out that the proposed approach and the algorithms are susceptible to be improved in future work. A theoretical contribution of the paper is a more generalized stable condition for parametric polynomial systems which serves as the base of the proposed algorithms for computing comprehensive Gröbner bases. The authors say that this new stable condition may lead to more interesting results.

Recommendations

Cited in

(51)

Describes a project that uses

Uses Software

SINGULAR

This page was built for publication: An efficient method for computing comprehensive Gröbner bases

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1940934)