Abstract
We consider three modifications of our basic involutive algorithm for computing polynomial Janet bases. These modifications, which are related to degree-compatible monomial orders, yield specific selection strategies for nonmultiplicative prolongations. Using a standard database of benchmarks designed for testing programs computing Gröbner bases, we compare these algorithmic modifications (in terms of their efficiency) with Faugére’s F 4 algorithm, which is built in the Magma computer algebra system.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Gerdt, V. P. and Blinkov, Yu. A., Involutive Bases of Polynomial Ideals, Math. Comput. Simulation, 1998, vol. 45, pp. 519–542, http://arXiv.org/math.AC/9912027; Minimal Involutive Bases, Math. Comput. Simulation, 1998, vol. 45, pp. 543–560, http://arXiv.org/math.AC/9912029.
Gerdt, V. P. and Blinkov, Yu. A., Involutive Division of Monomials, Programmirovanie, 1998, vol. 24, no. 6, pp. 283–285.
Janet, M., Leçons sur les systémes d’equations aux dérivées partielles, Cahiers Scientifiques, IV, Paris: Gauthier-Villars, 1929.
Gerdt, V. P., Blinkov, Yu. A., and Yanovich, D. A., Construction of Janet Bases. I. Monomial Bases, Proc. of the 4th Int. Conf. Computer Algebra in Scientific Computing CASC-2001 (Konstanz, Germany, 2001), Ganzha, V. G., Mayr, E. W., and Vorozhtsov, E. V., Eds., Berlin: Springer, 2001, pp. 233–247; II. Polynomial Bases, pp. 249–263.
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., NATO Science Series, IOS, 2005, vol. 196, pp. 199–225; http://arXiv.org/math.AC/0501111.
Gerdt, V. P. and Blinkov, Yu. A., Janet-Like Monomial Division. Janet-Like Gröbner Bases, Lecture Notes in Computer Science (Proc. of the 8th Int. Conf. Computer Algebra in Scientific Computing CASC-2005), Berlin: Springer, 2005, pp. 174–195.
Buchberger, B., Gröbner Bases: An Algorithmic Method in Polynomial Ideal Theory, in Recent Trends in Multidimensional System Theory, Bose, N.K., Ed., Dordrecht: Reidel, 1985, pp. 184–232.
Giovinni, A., Mora, T., Niesi, G., Robbiano, L., and Traverso, C., One Sugar Cube, Please, or Selection Strategies in the Buchberger Algorithm, Proc. of ISSAC’91, New York: ACM, 1991, pp. 49–54.
Gerdt, V. P. and Blinkov, Yu. A., On Computing Janet Bases for Degree-Compatible Orderings, Proc. of 10th Rhine Workshop on Computer Algebra (Basel, Switzerland, 2006), Basel, 2006, pp. 107–117, http://arXiv.org/math.AC/0603161.
Faugère, J. C., Gianni, P., Lazard, D., and Mora, T., Efficient Computation of Zero-Dimensional Gröbner Bases by Change of Ordering, J. Symbolic Computation, 1993, vol. 16, pp. 329–344.
Collart, S., Kalkbrener, M., and Mall, D., Converting Bases with the Gröbner Walk, J. Symbolic Computation, 1997, vol. 24, pp. 465–469.
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.
Bigatti, A. M., La Scala, R., and Robbiano, L., Computing Toric Ideals, J. Symbolic Computation, 1999, vol. 27, pp. 351–365.
Conti, P. and Traverso, C., Buchberger Algorithm and Integer Programming, Lecture Notes in Computer Science (Proc. AAECC-9), Berlin: Springer, 1991, vol. 539, pp. 130–139.
Author information
Authors and Affiliations
Additional information
Original Russian Text © V.P. Gerdt, Yu.A. Blinkov, 2007, published in Programmirovanie, 2007, Vol. 33, No. 3.
Rights and permissions
About this article
Cite this article
Gerdt, V.P., Blinkov, Y.A. On selection of nonmultiplicative prolongations in computation of Janet bases. Program Comput Soft 33, 147–153 (2007). https://doi.org/10.1134/S0361768807030048
Received:
Issue Date:
DOI: https://doi.org/10.1134/S0361768807030048