Volume 19, Issue 1 (4-2024)
IJMSI 2024, 19(1): 117-133 |
Back to browse issues page
Download citation:
BibTeX | RIS | EndNote | Medlars | ProCite | Reference Manager | RefWorks
Send citation to:
BibTeX | RIS | EndNote | Medlars | ProCite | Reference Manager | RefWorks
Send citation to:
Dehghani Darmain M, Hashemi A. A Parametric $ F_4 $ Algorithm. IJMSI 2024; 19 (1) :117-133
URL: http://ijmsi.ir/article-1-1718-en.html
URL: http://ijmsi.ir/article-1-1718-en.html
Abstract:
In this paper, we present a parametric F4 algorithm (socalled PF4) which can be considered as a generalization of Faugére’s F4 algorithm [8] to polynomial ideals with parametric coefficients. Our approach is based on the F4 algorithm, Montes DisPGB algorithm [21] and the parametric linear algebra method developed in [6]. The PF4 algorithm takes as input a parametric polynomial ideal and two monomial orderings on the variables and the parameters and returns a Gröbner system of the ideal with respect to a compatible elimination product of the given monomial orderings. We have implemented our new algorithm in Maple and give timings to compare its performance with those of (our implementation) of the Kapur et al. algorithm [16] and the DisPGB algorithm [21].
Keywords: Gröbner bases, Gröbner systems, F4 algorithm, PF4 algorithm, PGBMain algorithm, DisPGB algorithm.
Type of Study: Research paper |
Subject:
General
References
1. 1. T. Becker, V. Weispfenning, Gr¨obner Bases: a Computational Approach to Commutative Algebra, New York: Springer-Verlag, 1993.
2. B. Buchberger, Ein Algorithmus zum Auffinden der Basiselemente des Restklassen Ringes nach einem Nulldimensionalen Polynomideal, Innsbruck: Univ. Innsbruck, Mathematisches Institut (Diss.), 1965.
3. B. Buchberger, A Criterion for Detecting Unnecessary Reductions in the Construction of Gr¨obner Bases, Symbolic and algebraic computation, EUROSAM '79, int. Symp., Marseille 1979, Lect. Notes Comput. Sci., 72, (1979), 3-21. [DOI:10.1007/3-540-09519-5_52]
4. B. Buchberger, Bruno Buchberger's Ph.D. Thesis 1965: An Algorithm for Finding the Basis Elements of the Residue Class Ring of a Zero Dimensional Polynomial Ideal Translation from the German, J. Symb. Comput., 41(3-4), (2006), 475-511. [DOI:10.1016/j.jsc.2005.09.007]
5. D. Cox, A. Little, D. O'Shea Ideals, Varieties, and Algorithms. An introduction to Computational Algebraic Geometry and Commutative Algebra, 4th edition, Springer, 2015. [DOI:10.1007/978-3-319-16721-3]
6. M. Dehghani Darmian, A. Hashemi, Parametric FGLM Algorithm, J. Symb. Comput., 82, (2017), 38-56. [DOI:10.1016/j.jsc.2016.12.006]
7. M. Dehghani Darmian, A. Hashemi, A. Montes, Erratum to "A new algorithm for discussing Gr¨obner bases with parameters" [J. Symbolic Comput. 33 (1-2) (2002) 183-208], J. Symb. Comput., 46(10), (2011), 1187-1188. [DOI:10.1016/j.jsc.2011.05.002]
8. J.-C. Faug'ere, A New Efficient Algorithm for Computing Gr¨obner Bases (F4), J. Pure Appl. Algebra, 139(1-3), (1999), 61-88. [DOI:10.1016/S0022-4049(99)00005-5]
9. J.-C. Faug'ere, A New Efficient Algorithm for Computing Gr¨obner Bases without Reduction to Zero (F5), In Proceedings of the 2002 international symposium on symbolic and algebraic computation, ISSAC 2002, Lille, France, July 07-10, 2002. New York, ACM Press, (2002), 75-83.
10. R. Gebauer, H. M¨oller, On an Installation of Buchberger's Algorithm, J. Symb. Comput., 6(2-3), (1988), 275-286. [DOI:10.1016/S0747-7171(88)80048-8]
11. A. Hashemi, M. Dehghani Darmian, M. Barkhordar, Gr¨obner Systems Conversion, Math. Comput. Sci., 11(1), (2017), 61-77. [DOI:10.1007/s11786-017-0295-3]
12. A. Hashemi, M. Dehghani Darmian, B. M.-Alizadeh, Applying Buchberger's Criteria on Montes's DisPGB Algorithm, Bull. Iran. Math. Soc., 38(3), (2012), 715-724.
13. A. Hashemi, B. M.-Alizadeh, M. Dehghani Darmian, Minimal Polynomial Systems for Parametric Matrices, Linear Multilinear Algebra, 61(2), (2013), 265-272. [DOI:10.1080/03081087.2012.670235]
14. M. Kalkbrener, On the Complexity of Gr¨obner Bases Conversion, J. Symb. Comput., 28(1-2), (1999), 265-273. [DOI:10.1006/jsco.1998.0276]
15. D. Kapur, An Approach for Solving Systems of Parametric Polynomial Equations, In Saraswat, Vijay, Van Hentenryck, Pascal (Eds.), Principles and Practice of Constraint Programming. MIT Press, (1995), 217-224.
16. D. Kapur, Y. Sun, D. Wang, A New Algorithm for Computing Comprehensive Gr¨obner Systems, In Proceedings of the 35th international symposium on symbolic and algebraic computation, ISSAC 2010, Munich, Germany, July 25-28, 2010. New York, NY: Association for Computing Machinery (ACM), (2010), 29-36. [DOI:10.1145/1837934.1837946]
17. D. Kapur, Y. Sun, D. Wang, An Efficient Algorithm for Computing a Comprehensive Gr¨obner System of a Parametric Polynomial System, J. Symb. Comput., 49, (2013), 27-44. [DOI:10.1016/j.jsc.2011.12.015]
18. D. Lazard, Gr¨obner Bases, Gaussian Elimination and Resolution of Systems of Algebraic Equations, Computer algebra, EUROCAL '83, Proc. Conf., London 1983, Lect. Notes Comput. Sci., 162, (1983), 146-156. [DOI:10.1007/3-540-12868-9_99]
19. M. Manubens, A. Montes, Improving the DisPGB Algorithm Using the Discriminant Ideal, J. Symb. Comput., 41(11), (2006), 1245-1263. [DOI:10.1016/j.jsc.2005.09.013]
20. M. Manubens, A. Montes, Minimal Canonical Comprehensive Gr¨obner Systems, J. Symb. Comput., 44(5), (2009), 463-478. [DOI:10.1016/j.jsc.2007.07.022]
21. A. Montes, A New Algorithm for Discussing Gr¨obner Bases with Parameters, J. Symb. Comput., 33(2), (2002), 183-208. [DOI:10.1006/jsco.2001.0504]
22. A. Montes, The Gr¨obner Cover, 27, Cham: Springer, 2018.
23. A. Montes, J. Castro, Solving the Load Flow Problem Using the Gr¨obner Basis, SIGSAM Bull., 29(1), (1995), 1-13. [DOI:10.1145/216685.216686]
24. A. Montes, M. Wimber, Gr¨obner Bases for Polynomial Systems with Parameters, J. Symb. Comput., 45(12), (2010), 1391-1425. [DOI:10.1016/j.jsc.2010.06.017]
25. K. Nabeshima, A Speed-up of the Algorithm for Computing Comprehensive Gr¨obner Systems, In Proceedings of the 2007 international symposium on symbolic and algebraic computation, ISSAC 2007, Waterloo, ON, Canada, July 29-August 1, 2007. New York, NY: Association for Computing Machinery (ACM), (2007), 299-306. [DOI:10.1145/1277548.1277589]
26. W. Y. Sit, M. Wimber, An Algorithm for Solving Parametric Linear Systems, J. Symb. Comput., 13(4), (1992), 353-394. [DOI:10.1016/S0747-7171(08)80104-6]
27. A. Suzuki, Y. Sato, A Simple Algorithm to Compute Comprehensive Gr¨obner Bases Using Gr¨obner Bases, In Proceedings of the 2006 international symposium on symbolic and algebraic computation, ISSAC 06, Genova, Italy, July 9-12, 2006. New York, NY: Association for Computing Machinery (ACM), (2006), 326-331. [DOI:10.1145/1145768.1145821]
28. V. Weispfenning, Comprehensive Gr¨obner Bases, J. Symb. Comput., 14(1), (1992), 1-29. [DOI:10.1016/0747-7171(92)90023-W]
29. V. Weispfenning, Canonical Comprehensive Gr¨obner Bases, J. Symb. Comput., 36(3-4), (2003), 669-683. [DOI:10.1016/S0747-7171(03)00099-3]
30. M. Wimber, Gr¨obner Bases for Families of Affine or Projective Schemes, J. Symb. Comput., 42(8), (2007), 803-834. [DOI:10.1016/j.jsc.2007.05.001]
| Rights and permissions | |
 |
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License. |
