Top

Mathematics in Computer Science

Published in:

21-05-2021

Relative Gröbner and Involutive Bases for Ideals in Quotient Rings

Authors: Amir Hashemi, Matthias Orth, Werner M. Seiler

Published in: Mathematics in Computer Science | Issue 3/2021

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

We extend the concept of Gröbner bases to relative Gröbner bases for ideals in and modules over quotient rings of a polynomial ring over a field. We develop a “relative” variant of both Buchberger’s criteria for avoiding reductions to zero and Schreyer’s theorem for a Gröbner basis of the syzygy module. As main contribution, we then introduce the novel notion of relative involutive bases and present an algorithm for their explicit construction. Finally, we define the new notion of relatively quasi-stable ideals and exploit it for the algorithmic determination of coordinates in which finite relative Pommaret bases exist.

previous article An Involutive GVW Algorithm and the Computation of Pommaret Bases

next article Creative Telescoping on Multiple Sums

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

We omit the index \({\mathcal {I}}\), if it is clear from the context by which ideal we factor.

It should be noted that, by Lemma 7.3, it follows that this change may be sparser than the change that we need to transform \({{\,\mathrm{{\mathcal {J}}}\,}}\) into quasi-stable position.

Becker, T., Weispfenning, V.: Gröbner Bases: A Computational Approach to Commutative Algebra. In: Cooperation with Heinz Kredel, vol. 141. Springer, New York (1993)

Berkesch, C., Schreyer, F.-O.: Syzygies, finite length modules, and random curves. In: Commutative Algebra and Noncommutative Algebraic Geometry. Vol. I: Expository articles, pp. 25–52. Cambridge University Press, Cambridge (2015)

Buchberger, B.: A criterion for detecting unnecessary reductions in the construction of Gröbner-bases. Symbolic and algebraic computation, EUROSAM ’79, International Symposium, Marseille 1979, Lecture Notes Computer Science 72, 3–21 (1979)

Buchberger, B.: Ein Algorithmus zum Auffinden der Basiselemente des Restklassenringes nach einem nulldimensionalen Polynomideal. Ph.D. thesis, Universität Innsbruck (1965)

Buchberger, B.: 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), 475–511 (2006)

Ceria, M., Mora, T.: Buchberger–Weispfenning theory for effective associative rings. J. Symb. Comput. 83, 112–146 (2017)MathSciNetCrossRef

Ceria, M., Mora, T.: Toward involutive bases over effective rings. Appl. Algebra Eng. Commun. Comput. 31, 359–387 (2020)MathSciNetCrossRef

Cox, D.A., Little, J., O’Shea, D.: Using Algebraic Geometry, vol. 185, 2nd edition. Springer, New York (2005)

Cox, D.A., Little, J., O’Shea, D.: Ideals, Varieties, and Algorithms. An Introduction to Computational Algebraic Geometry and Commutative Algebra. 4th revised ed. Cham: Springer (2015)

10.

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)MathSciNetCrossRef

11.

Faugère, J.-C.: A new efficient algorithm for computing Gröbner bases without reduction to zero \((F_5)\). In: Proceedings of the 2002 International Symposium on Symbolic and Algebraic Computation, ISSAC 2002, Lille, France, July 07–10, 2002, pp. 75–83. New York, NY: ACM Press (2002)

12.

Gao, S., Volny, F.I.V., Wang, M.: A new framework for computing Gröbner bases. Math. Comput. 85(297), 449–465 (2016)CrossRef

13.

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, 2004, pp. 199–225. Amsterdam: IOS Press (2005)

14.

Gerdt, V.P., Blinkov, Y.A.: Involutive bases of polynomial ideals. Math. Comput. Simul. 45(5–6), 519–541 (1998)MathSciNetCrossRef

15.

Gerdt, V.P., Blinkov, Y.A.: Minimal involutive bases. Math. Comput. Simul. 45(5–6), 543–560 (1998)MathSciNetCrossRef

16.

Hashemi, A., Schweinfurter, M., Seiler, W.M.: Deterministic genericity for polynomial ideals. J. Symb. Comput. 86, 20–50 (2018)MathSciNetCrossRef

17.

Hausdorf, M., Sahbi, M., Seiler, W.M.: \(\delta \)- and quasi-regularity for polynomial ideals. In: Calmet, J., Seiler, W.M., Tucker, R.W. (eds.) Global Integrability of Field Theories, pp. 179–200. Universitätsverlag Karlsruhe, Karlsruhe (2006)

18.

Hausdorf, M., Seiler, W.M.: An efficient algebraic algorithm for the geometric completion to involution. Appl. Alg. Eng. Commun. Comput. 13, 163–207 (2002)MathSciNetCrossRef

19.

Janet, M.: Sur les systèmes d’équations aux dérivées partielles. C. R. Acad. Sci. Paris 170, 1101–1103 (1920)

20.

Kapur, D., Cai, Y.: An algorithm for computing a Gröbner basis of a polynomial ideal over a ring with zero divisors. Math. Comput. Sci. 2(4), 601–634 (2009)MathSciNetCrossRef

21.

La Scala, R., Stillman, M.: Strategies for computing minimal free resolutions. J. Symb. Comput. 26(4), 409–431 (1998)

22.

Möller, H.M., Mora, T., Traverso, C.: Gröbner bases computation using syzygies. In: International Symposium on Symbolic and Algebraic Computation 92. ISSAC 92. Berkeley, CA, USA, July 27–29, 1992, pp. 320–328. Baltimore, MD: ACM Press (1992)

23.

Mora, T.: De Nugis Groebnerialium 4: Zacharias, Spears, Möller. In Proceedings of the 2015 international symposium on symbolic and algebraic computation, ISSAC 2015, Bath, United Kingdom, July 06–9, 2015., pages 191–198. New York, NY: ACM Press, (2015)

24.

Mora, T.: Zacharias representation of effective associative rings. J. Symb. Comput. 99, 147–188 (2020)MathSciNetCrossRef

25.

Norton, G.H., Sălăgean, A.: Strong Gröbner bases for polynomials over a principal ideal ring. Bull. Aust. Math. Soc. 64(3), 505–528 (2001)CrossRef

26.

Pommaret, J.-F.: Systems of Partial Differential Equations and Lie Pseudogroups. Gordon and Breach Science Publishers (1978)

27.

Schreyer, F.-O.: Die Berechnung von Syzygien mit dem verallgemeinerten Weierstrass’schen Divisionssatz. Master’s thesis, University of Hamburg, Germany, (1980)

28.

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)MathSciNetCrossRef

29.

Seiler, W.M.: Involution. The Formal Theory of Differential Equations and its Applications in Computer Algebra. Springer, Berlin (2010)

30.

Seiler, W.M.: Effective genericity, \(\delta \)-regularity and strong Noether position. Commun. Algebra 40(10), 3933–3949 (2012)MathSciNetCrossRef

31.

Semenov, A.: On connection between constructive involutive divisions and monomial orderings. In: Computer Algebra in Scientific Computing. 9th International Workshop, CASC 2006, Chişinău, Moldova, September 11–15, 2006. Proceedings, pp. 261–278. Berlin: Springer (2006)

32.

Spear, D.: A constructive approach to commutative ring theory. In: Proceedings of 1977 Macsyma Users’ Conference, pp. 369–376. NASA CP-2012 (1977)

33.

Zacharias, G.: Generalized Gröbner bases in commutative polynomial rings. Master’s thesis, MIT, (1978)

34.

Zharkov, A.Y., Blinkov, Y.A.: Involution approach to investigating polynomial systems. Math. Comput. Simul. 42(4), 323–332 (1996)MathSciNetCrossRef

Title: Relative Gröbner and Involutive Bases for Ideals in Quotient Rings
Authors: Amir Hashemi
Matthias Orth
Werner M. Seiler
Publication date: 21-05-2021
Publisher: Springer International Publishing
Published in: Mathematics in Computer Science / Issue 3/2021
Print ISSN: 1661-8270
Electronic ISSN: 1661-8289
DOI: https://doi.org/10.1007/s11786-021-00513-4

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Other articles of this Issue 3/2021

A Symbolic-Numeric Validation Algorithm for Linear ODEs with Newton–Picard Method

Symbolic Computations of the Equilibrium Orientations of a System of Two Connected Bodies Moving on a Circular Orbit Around the Earth

Foreword, with a Dedication to Vladimir Gerdt

Creative Telescoping on Multiple Sums

Algorithmic Reduction of Biological Networks with Multiple Time Scales

An Involutive GVW Algorithm and the Computation of Pommaret Bases

Premium Partner