Abstract
In this paper, a parallel algorithm for computation of polynomial Janet bases is considered. After construction of a Janet basis, a reduced Gröbner basis (which is a subset of the Janet basis) is extracted from it without any additional reductions. The algorithm discussed is an improved version of an earlier suggested parallel algorithm. The efficiency of a C implementation of the algorithm and its scalability are illustrated by way of the standard test examples that are often used for comparing various algorithms and codes for computing Gröbner bases.
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
Faugére, J.C., Parallelization of Gröbner Basis, in Lecture Notes. Series in Computing 5 (PASCO’94), Singapore: World Sci., 1994, pp. 124–132.
Attardi, G. and Traverso, C., Strategy-Accurate Parallel Buchberger Algorithm, J. Symb. Comp., 1996, vol. 11, pp. 411–425.
Amrheim, B., Gloor, O., and Küchlin, W., A Case Study of Multi-Threaded Gröbner Basis Completion, Proc. of ISSAC’96, 1996, pp. 95–102.
Buchberger, B., Gröbner Bases: An Algorithmic Method in Polynomial Ideal Theory, Recent Trends in Multidimensional System Theory, Bose, N.K., Ed., Dordrecht: Reidel, 1985, pp. 184–232. Translated under the title Komp’yuternaya algebra. Simvol’nye i algebraicheskie vychisleniya, Moscow: Mir, 1986.
Gianni, P., Mora, T., Niesi, G., Robbiano, L., and Traverso, K., “One Sugar Cube, Please” or Selection Strategies in Buchberger Algorithm, Proc. of ISSA’91, ACM, 1991, pp. 49–54.
Gerdt, V.P. and Blinkov, Yu.A., Involutive Bases of Polynomial Ideals, Math. Comput. Simulation, 1998, vol. 45, pp. 519–542.
Gerdt, V.P. and Blinkov, Yu.A., Minimal Involutive Bases, Math. Comput. Simulation, 1998, vol. 45, pp. 543–560.
Gerdt, V.P., On an Algorithmic Optimization in Computation of Involutive Bases, Programmirovanie, 2002, no. 2, pp. 62–65.
Yanovich, D.A., Parallelization of an Algorithm for Computation of Involutive Janet Bases, Programmirovanie, 2002, no. 2, pp. 66–69.
Gerdt, V.P. and Yanovich, D.A., Parallelism in Computing Janet Bases, Proc. of the Workshop on Under-and Overdetermined Systems of Algebraic or Differential Equations, Calmet, J., Hausdorf, M., and Seiler, W.M., Eds., Karlsruhe: Institute of Algorithms and Cognitive Systems, Univ. of Karlsruhe, 2002, pp. 47–56.
Gerdt, V.P., Blinkov, Yu.A., and Yanovich, D.A., Construction of Janet Bases II. Polynomial Bases, Proc. of the Conf. “Computer Algebra in Scientific Computing” (CASC’01), (2001), Berlin: Springer, 2001.
http://www.swox.com/gmp.
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. and Blinkov, Yu.A., Involutive Divisions of Monomials, Programmirovanie, 1998, no. 6, pp. 22–24.
http://www.gentoo.org.
Bini, D. and Mourrain, B., Polynomial Test Suite, 1996, http://www-sop.inria.fr/saga/POL.
Verschelde, J., The Database with Test Examples, http://www.math.uic.edu/~jan/demo.html.
Apel, J. and Hemmecke, R., Detecting Unnecessary Reductions in an Involutive Basis Computation, RISC Linz Report No 02-22, 2002.
Calmet, J., Hausdorf, M., and Seiler, W.M., A Constructive Introduction to Involution, Proc. Int. Symp. Applications of Computer Algebra — ISACA 2000, Akerkar, R., Ed., New Delhi: Allied Publishers, 2001, pp. 33–50.
Author information
Authors and Affiliations
Additional information
Translated from Programmirovanie, Vol. 31, No. 2, 2005.
Original Russian Text Copyright © 2005 by Gerdt, Yanovich.
Rights and permissions
About this article
Cite this article
Gerdt, V.P., Yanovich, D.A. Parallel computation of Janet and Gröbner bases over rational numbers. Program Comput Soft 31, 73–80 (2005). https://doi.org/10.1007/s11086-005-0016-6
Received:
Issue Date:
DOI: https://doi.org/10.1007/s11086-005-0016-6