[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

On the use of Buchberger criteria in G2V algorithm for calculating Gröbner bases

  • Published:
Programming and Computer Software Aims and scope Submit manuscript

Abstract

It has been experimentally demonstrated by Faugère that his F5 algorithm is the fastest algorithm for calculating Gröbner bases. Computational efficiency of F5 is due to not only applying linear algebra but also using the new F5 criterion for revealing useless zero reductions. At the ISSAC 2010 conference, Gao, Guan, and Volny presented G2V, a new version of the F5 algorithm, which is simpler than the original version of the algorithm. However, the incremental structure of G2V used in the algorithm for applying the F5 criterion is a serious obstacle from the point of view of application of Buchberger’s second criterion. In this paper, a modification of the G2V algorithm is presented, which makes it possible to use both Buchberger criteria. To experimentally study computational effect of the proposed modification, we implemented the modified algorithm in Maple. Results of comparison of G2V and its modified version on a number of test examples are presented.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

References

  1. Buchberger, B., Ein Algorithms zum Auffinden der Basiselemente des Restklassenrings nach einem nuildimensionalen Polynomideal, PhD Dissertation, Innsbruck, Univ. of Innsbruck, 1965.

    Google Scholar 

  2. Buchberger, B., A Criterion for Detecting Unnecessary Reductions in the Construction of Gröbner Bases, Lect. Notes Comput. Sci., Berlin: Springer, 1979, vol. 72, pp. 3–21.

    Google Scholar 

  3. Buchberger, B. and Winkler, F., Gröbner Bases and Applications, London Math. Society Lecture Note Series, 1998, vol. 251, Cambridge: Cambridge University Press.

    Google Scholar 

  4. Lazard, D., Gröbner Bases, Gaussian Elimination and Resolution of Systems of Algebraic Equations, Lect. Notes Comput. Sci., Berlin: Springer, 1983, vol., 162, pp. 146–156.

    Google Scholar 

  5. Gebauer, R. and Möller, H., On an Installation of Buchberger’s Algorithm, J. Symb. Comput., 1988, vol. 6, nos. 2–3, pp. 275–286.

    Article  MATH  Google Scholar 

  6. Faugère, J.-C., A New Efficient Algorithm for Computing Gröbner Bases (F 4), J. Pure Applied Algebra, 1999, vol. 139, nos. 1–3, pp. 61–68.

    Article  MATH  Google Scholar 

  7. Faugère, J.-C., A New Efficient Algorithm for Computing Gröbner Bases without Reduction to Zero (F 5), Proc. of ISSAC 2002, New York: ACM, 2002, pp. 75–83.

    Google Scholar 

  8. Ars, G. and Hashemi, A. Extended F5 Criteria, J. Symb. Comput., 2010, vol. 45, no. 12, pp. 1330–1340.

    Article  MathSciNet  MATH  Google Scholar 

  9. Eder, C. and Perry, J., F5C: A Variant of Faugère’s F5 Algorithm with Reduced Gröbner Bases, J. Symb. Comput., 2010, vol. 45, no. 12, pp. 1442–1458.

    Article  MathSciNet  MATH  Google Scholar 

  10. Gao, S., Guan, Y., and Volny, F. IV, A New Incremental Algorithm for Computing Gröbner Bases, Proc. of ISSAC’10, 2010, ACM, pp. 13–19.

    Google Scholar 

  11. Gao, S., Volny, F. IV, and Guan, Y., A New Algorithm for Computing Gröbner Bases, Preprint, 2011. http://www.math.clemson.edu/~sgao/pub.html.

    Google Scholar 

  12. Ars, G., Applications des bases de Gröbner à la cryptographie, PhD Dissertation, Rennes: Universite — de Rennes, 2004.

    Google Scholar 

  13. Gash, G.M., On Efficient Computation of Gröbner Bases, PhD Dissertation, Indiana University, 2008. http://gradworks.umi.com/3330795.pdf

    Google Scholar 

  14. Becker, T. and Weispfenning, V., Gröbner Bases. A Computational Approach to Commutative Algebra, Graduate Texts in Mathematics, vol. 141, New York: Springer, 1993.

    Google Scholar 

  15. Eder, C. and Perry, J., Signature-based Algorithms to Compute Gröbner Bases, Proc. of ISSAC’11, 2011, ACM, pp. 99–106.

    Google Scholar 

  16. Mora, T., Solving Polynomial Equation Systems II: Macaulay’s Paradigm and Gröbner Technology, Encyclopedia of Mathematics and Its Applications, vol. 99, Cambridge University Press, 2005.

  17. Hashemi, A. and Alizadeh, B.M., Applying IsRewritten Criterion on Buchberger Algorithm, Theor. Comput. Sci., 2011, vol. 412, no. 35, pp. 4592–4603.

    Article  MATH  Google Scholar 

  18. Huang, L., A New Conception for Computing Gröbner Basis and Its Applications, 2010. arXiv:math.SC/1012.5424.

    Google Scholar 

  19. Gerdt, V.P., Involutive Algorithms for Computing Gröbner Bases, Computational Commutative and Non-Commutative Algebraic Geometry, Cojocaru, S., Pfister, G., and Ufnarovski, V., Eds., Amsterdam: IOS, 2005, pp. 199–225. arXiv:math.AC/0501111.

    Google Scholar 

  20. Bini, D. and Mourrain, B., Polynomial Test Suite. http://www-sop.inria.fr/saga/POL/

Download references

Author information

Authors and Affiliations

  1. Laboratory of Information Technologies, Joint Institute for Nuclear Research, Dubna, Moscow oblast, 141980, Russia

    Vladimir P. Gerdt

  2. Department of Mathematical Sciences, Isfahan University of Technology, Isfahan, 84156-83111, Iran

    Amir Hashemi

Authors
  1. Vladimir P. Gerdt
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Amir Hashemi
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Vladimir P. Gerdt.

Additional information

Original Russian Text © Vladimir P. Gerdt, Amir Hashemi, 2013, published in Programmirovanie, 2013, Vol. 39, No. 2.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Gerdt, V.P., Hashemi, A. On the use of Buchberger criteria in G2V algorithm for calculating Gröbner bases. Program Comput Soft 39, 81–90 (2013). https://doi.org/10.1134/S0361768813020047

Download citation

  • Received:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1134/S0361768813020047

Keywords

Search

Navigation