Abstract
We investigate the application of syzygies for efficiently computing (finite) Pommaret bases. For this purpose, we first describe a non-trivial variant of Gerdt’s algorithm [10] to construct an involutive basis for the input ideal as well as an involutive basis for the syzygy module of the output basis. Then we apply this new algorithm in the context of Seiler’s method to transform a given ideal into quasi stable position to ensure the existence of a finite Pommaret basis [19]. This new approach allows us to avoid superfluous reductions in the iterative computation of Janet bases required by this method. We conclude the paper by proposing an involutive variant of the signature based algorithm of Gao et al. [8] to compute simultaneously a Gröbner basis for a given ideal and for the syzygy module of the input basis. All the presented algorithms have been implemented in Maple and their performance is evaluated via a set of benchmark ideals.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
The Maple code of the implementations of our algorithms and examples are available at http://amirhashemi.iut.ac.ir/softwares.
References
Binaei, B., Hashemi, A., Seiler, W.M.: Improved computation of involutive bases. In: Gerdt, V., Koepf, W., Seiler, W., Vorozhtsov, E. (eds.) CASC 2016. LNCS, vol. 9890, pp. 58–72. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-45641-6_5
Buchberger, B.: A criterion for detecting unnecessary reductions in the construction of Gröbner-bases. In: Ng, E.W. (ed.) EUROSM 1979. LNCS, vol. 72, pp. 3–21. Springer, Heidelberg (1979). https://doi.org/10.1007/3-540-09519-5_52
Buchberger, B.: Ein Algorithmus zum Auffinden der Basiselemente des Restklassenringes nach einem nulldimensionalen Polynomideal. University of Innsbruck, Mathematisches Institut (Diss.), Innsbruck (1965)
Cox, D., Little, J., O’Shea, D.: Ideals, Varieties, and Algorithms, 3rd edn. Springer, New York (2007). https://doi.org/10.1007/978-0-387-35651-8
Cox, D.A., Little, J., O’Shea, D.: Using Algebraic Geometry. Graduate Texts in Mathematics, vol. 185, 2nd edn. Springer, New York (2005). https://doi.org/10.1007/b138611
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). https://doi.org/10.1016/S0022-4049(99)00005-5
Faugère, J.C.: A new efficient algorithm for computing Gröbner bases without reduction to zero \((F_5)\). In: Proceedings of ISSAC 2002, pp. 75–83 (2002)
Gao, S., Volny, F.I., Wang, M.: A new framework for computing Gröbner bases. Math. Comput. 85(297), 449–465 (2016). https://doi.org/10.1090/mcom/2969
Gebauer, R., Möller, H.: On an installation of Buchberger’s algorithm. J. Symb. Comput. 6(2–3), 275–286 (1988). https://doi.org/10.1016/S0747-7171(88)80048-8
Gerdt, V.P.: Involutive algorithms for computing Gröbner bases. In: Computational Commutative and Non-commutative Algebraic Geometry. Proceedings of the NATO Advanced Research Workshop, pp. 199–225. IOS Press, Amsterdam (2005)
Gerdt, V.P., Blinkov, Y.A.: Involutive bases of polynomial ideals. Math. Comput. Simul. 45(5–6), 519–541 (1998). https://doi.org/10.1016/S0378-4754(97)00127-4
Gerdt, V.P., Hashemi, A., Alizadeh, B.M.: Involutive bases algorithm incorporating F\(_5\) criterion. J. Symb. Comput. 59, 1–20 (2013). https://doi.org/10.1016/j.jsc.2013.08.002
Hashemi, A., Schweinfurter, M., Seiler, W.: Deterministic genericity for polynomial ideals. J. Symb. Comput. 86, 20–50 (2018)
Janet, M.: Sur les systèmes d’équations aux dérivées partielles. C. R. Acad. Sci. Paris 170, 1101–1103 (1920)
Lazard, D.: Gröbner bases, Gaussian elimination and resolution of systems of algebraic equations. In: van Hulzen, J.A. (ed.) EUROCAL 1983. LNCS, vol. 162, pp. 146–156. Springer, Heidelberg (1983). https://doi.org/10.1007/3-540-12868-9_99
Möller, H., Mora, T., Traverso, C.: Gröbner bases computation using syzygies. In: Proceedings of ISSAC 1992, pp. 320–328 (1992)
Pommaret, J.: Systems of Partial Differential Equations and Lie Pseudogroups. Gordon and Breach Science Publishers, Philadelphia (1978)
Schreyer, F.O.: Die Berechnung von Syzygien mit dem verallgemeinerten Weierstrass’schen Divisionssatz. Master’s thesis, University of Hamburg, Germany (1980)
Seiler, W.M.: A combinatorial approach to involution and \(\delta \)-regularity. II: structure analysis of polynomial modules with Pommaret bases. Appl. Algebra Eng. Commun. Comput. 20(3–4), 261–338 (2009). https://doi.org/10.1007/s00200-009-0101-9
Seiler, W.M.: Involution. The Formal Theory of Differential Equations and Its Applications in Computer Algebra. Springer, Berlin (2001). https://doi.org/10.1007/978-3-642-01287-7
Wall, B.: On the computation of syzygies. SIGSAM Bull. 23(4), 5–14 (1989)
Zharkov, A., Blinkov, Y.: Involution approach to investigating polynomial systems. Math. Comput. Simul. 42(4), 323–332 (1996). https://doi.org/10.1016/S0747-7171(88)80048-8
Acknowledgments
The research of the second author was in part supported by a grant from IPM (No. 95550420). The work of the third author was partially performed as part of the H2020-FETOPEN-2016-2017-CSA project \(SC^{2}\) (712689).
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2018 Springer Nature Switzerland AG
About this paper
Cite this paper
Binaei, B., Hashemi, A., Seiler, W.M. (2018). Computation of Pommaret Bases Using Syzygies. In: Gerdt, V., Koepf, W., Seiler, W., Vorozhtsov, E. (eds) Computer Algebra in Scientific Computing. CASC 2018. Lecture Notes in Computer Science(), vol 11077. Springer, Cham. https://doi.org/10.1007/978-3-319-99639-4_4
Download citation
DOI: https://doi.org/10.1007/978-3-319-99639-4_4
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-99638-7
Online ISBN: 978-3-319-99639-4
eBook Packages: Computer ScienceComputer Science (R0)