Involutive bases algorithm incorporating F\(_5\) criterion. (English) Zbl 1435.68391
Summary: Faugère’s F\(_5\) algorithm [J.-C. Faugère, in: Proceedings of the 2002 international symposium on symbolic and algebraic computation, ISSAC 2002. New York, NY: ACM Press. 75–83 (2002; Zbl 1072.68664)] is the fastest known algorithm to compute Gröbner bases. It has a signature-based and an incremental structure that allow to apply the F\(_5\) criterion for deletion of unnecessary reductions. In this paper, we present an involutive completion algorithm which outputs a minimal involutive basis. Our completion algorithm has a non-incremental structure and in addition to the involutive form of Buchberger’s criteria it applies the F\(_5\) criterion whenever this criterion is applicable in the course of completion to involution. In doing so, we use the G\(^2\)V form of the F\(_5\) criterion developed by S. Gao et al. [in: Proceedings of the 35th international symposium on symbolic and algebraic computation, ISSAC 2010. New York, NY: ACM Press. 13–19 (2010; Zbl 1321.68531)]. To compare the proposed algorithm, via a set of benchmarks, with the Gerdt-Blinkov involutive algorithm [V. P. Gerdt and Yu. A. Blinkov, Math. Comput. Simul. 45, 519–541 (1998; Zbl 1017.13500)] (which does not apply the F\(_5\) criterion) we use implementations of both algorithms done on the same platform in Maple.
MSC:
| 68W30 | Symbolic computation and algebraic computation |
| 13P10 | Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) |
Keywords:
involutive division; involutive bases; Gröbner bases; Buchberger’s criteria; F\(_5\) criterion; G\(^2\)V algorithmReferences:
| [1] | Apel, J., Theory of involutive divisions and an application to Hilbert function computations, J. Symb. Comput., 25, 6, 683-704 (1998) · Zbl 0943.68191 |
| [2] | Apel, J.; Hemmecke, R., Detecting unnecessary reductions in an involutive basis computation, J. Symb. Comput., 40, 4-5, 1131-1149 (2005) · Zbl 1120.13028 |
| [3] | Ars, G.; Hashemi, A., Extended \(F_5\) criteria, J. Symb. Comput., 45, 12, 1330-1340 (2010) · Zbl 1218.13014 |
| [4] | Becker, T.; Weispfenning, V., Gröbner Bases: A Computational Approach to Commutative Algebra (1993), Springer-Verlag: Springer-Verlag New York · Zbl 0772.13010 |
| [5] | Bini, D.; Mourrain, B., Polynomial test suite (1998) |
| [6] | Blinkov, Y. A.; Gerdt, V. P.; Cid, C. F.; Plesken, W.; Robertz, D., (Ganzha, V. G.; Mayr, E. W.; Vorozhtsov, E. V., The Maple Package “Janet”: I. Polynomial Systems and II. Linear Partial Differential Equations. The Maple Package “Janet”: I. Polynomial Systems and II. Linear Partial Differential Equations, Computer Algebra in Scientific Computing/CASC 2003 (2003), Institute of Informatics, Technical University of Munich: Institute of Informatics, Technical University of Munich Garching), 31-54 |
| [7] | Buchberger, B., Ein Algorithms zum Auffinden der Basiselemente des Restklassenrings nach einem nuildimensionalen Polynomideal (1965), Universität Innsbruck, PhD Dissertation · Zbl 1245.13020 |
| [8] | Buchberger, B., A Criterion for Detecting Unnecessary Reductions in the Construction of Gröbner Bases, Lect. Notes Comput. Sci., vol. 72, 3-21 (1979), Springer: Springer Berlin · Zbl 0417.68029 |
| [9] | (Buchberger, B.; Winkler, F., Gröbner Bases and Applications. Gröbner Bases and Applications, Lond. Math. Soc. Lect. Note Ser., vol. 251 (1998), Cambridge University Press: Cambridge University Press Cambridge) · Zbl 0883.00014 |
| [10] | Cox, D.; Little, J.; OʼShea, D., Using Algebraic Geometry, Graduate Texts in Math., vol. 185 (2005), Springer: Springer New York · Zbl 1079.13017 |
| [11] | Eder, C.; Perry, J., F5C: a variant of Faugèreʼs F5 algorithm with reduced Gröbner bases, J. Symb. Comput., 45, 12, 1442-1458 (2010) · Zbl 1227.13018 |
| [12] | Eder, C.; Perry, J., Signature-based algorithms to compute Gröbner bases, (Proc. of ISSACʼ11 (2011), ACM Press), 99-106 · Zbl 1323.68593 |
| [13] | Faugère, J.-C., A new efficient algorithm for computing Gröbner bases \((F_4)\), J. Pure Appl. Algebra, 139, 1-3, 61-88 (1999) · Zbl 0930.68174 |
| [14] | Faugère, J.-C., A new efficient algorithm for computing Gröbner bases without reduction to zero \((F_5)\), (Proc. ISSACʼ02 (2002), ACM Press), 75-83 · Zbl 1072.68664 |
| [15] | Gao, S.; Guan, Y.; Volny IV, F., A new incremental algorithm for computing Groebner bases, (Proc. ISSACʼ10 (2010), ACM Press), 13-19 · Zbl 1321.68531 |
| [16] | Gao, S.; Volny, F.; Wang, M., A new algorithm for computing Gröbner bases (2010), Preprint |
| [17] | Gebauer, R.; Möller, H., On an installation of Buchbergerʼs algorithm, J. Symb. Comput., 6, 2-3, 275-286 (1988) · Zbl 0675.13013 |
| [18] | Gerdt, V. P., On an algorithmic optimization in computation of involutive bases, Program. Comput. Softw., 28, 2, 62-65 (2002) · Zbl 1037.68063 |
| [19] | Gerdt, V. P., Involutive algorithms for computing Gröbner bases, (Cojocaru, S.; Pfister, G.; Ufnarovski, V., Computational Commutative and Non-Commutative Algebraic Geometry (2005), IOS: IOS Amsterdam), 199-225 · Zbl 1104.13012 |
| [20] | Gerdt, V. P.; Blinkov, Yu. A., Involutive bases of polynomial ideals, Math. Comput. Simul., 45, 519-542 (1998), Minimal involutive bases, 543-560 · Zbl 1017.13500 |
| [21] | Gerdt, V. P.; Blinkov, Yu. A., On selection of nonmultiplicative prolongations in computation of Janet bases, Program. Comput. Softw., 33, 3, 147-153 (2007) · Zbl 1147.68878 |
| [22] | Gerdt, V. P.; Blinkov, Yu. A., Specialized computer algebra system GINV, Program. Comput. Softw., 34, 112-123 (2008) · Zbl 1185.68867 |
| [23] | Gerdt, V. P.; Blinkov, Yu. A., Involutive Division Generated by an Antigraded Monomial Ordering, Lect. Notes Comput. Sci., vol. 6885, 158-174 (2011), Springer: Springer Berlin · Zbl 1344.68299 |
| [24] | Gerdt, V. P.; Yanovich, D. A., Effectiveness of involutive criteria in computation of polynomial Janet bases, Program. Comput. Softw., 32, 134-138 (2006) · Zbl 1103.68987 |
| [25] | Huang, L., A new conception for computing Gröbner basis and its applications (2010) |
| [26] | Janet, M., Les systèmes dʼéquations aux dérivées partielles, Journal de Mathématique, 3, 65-151 (1920) |
| [27] | Lazard, D., Gröbner Bases, Gaussian Elimination and Resolution of Systems of Algebraic Equations, Lect. Notes Comput. Sci., vol. 162, 146-156 (1983), Springer: Springer Berlin · Zbl 0539.13002 |
| [28] | Mora, T., Solving Polynomial Equation Systems II. Macaulayʼs Paradigm and Gröbner Technology, Encyclopedia of Mathematics and Its Applications, vol. 99 (2005), Cambridge University Press: Cambridge University Press Cambridge · Zbl 1161.13306 |
| [29] | Pan, S.; Hu, Y.; Wang, B., The termination of algorithms for computing Gröbner Bases (2012) |
| [30] | Galkin, V., Termination of original F5 (2012) |
| [31] | Pommaret, J.-F., Systems of Partial Differential Equations and Lie Pseudogroups, Mathematics and its Applications, vol. 14 (1978), Gordon & Breach Science Publishers: Gordon & Breach Science Publishers New York · Zbl 0418.35028 |
| [32] | Seiler, W. M., Involution - The Formal Theory of Differential Equations and its Applications in Computer Algebra (2010), Springer-Verlag: Springer-Verlag Berlin-Heidelberg · Zbl 1205.35003 |
| [33] | Sun, Y.; Wang, D., A generalized criterion for signature related Gröbner basis algorithms, (Proc. of ISSACʼ11 (2011), ACM Press), 337-344 · Zbl 1323.68630 |
| [34] | Sun, Y.; Wang, D., The F5 algorithm in Buchbergerʼs style, J. Syst. Sci. Complex., 24, 6, 1218-1231 (2011) · Zbl 1339.68322 |
| [35] | Thomas, J., Differential Systems (1937), American Mathematical Society: American Mathematical Society New York · JFM 63.0438.03 |
| [36] | Zharkov, A. Yu.; Blinkov, Yu. A., Involutive approach to investigating polynomial systems, Math. Comput. Simul., 42, 323-332 (1996) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
