nach oben

Mathematics in Computer Science

Erschienen in:

07.06.2021

An Involutive GVW Algorithm and the Computation of Pommaret Bases

verfasst von: Amir Hashemi, Thomas Izgin, Daniel Robertz, Werner M. Seiler

Erschienen in: Mathematics in Computer Science | Ausgabe 3/2021

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

The GVW algorithm computes simultaneously Gröbner bases of a given ideal and of the syzygy module of the given generating set. In this work, we discuss an extension of it to involutive bases. Pommaret bases play here a special role in several respects. We distinguish between a fully involutive GVW algorithm which determines involutive bases for both the given ideal and the syzygy module and a semi-involutive version which computes for the syzygy module only an ordinary Gröbner basis. A prototype implementation of the developed algorithms in Maple is described.

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

Nächster Artikel Relative Gröbner and Involutive Bases for Ideals in Quotient Rings

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren

By this we mean that they aimed to compute an involutive basis of an ideal and a Gröbner basis of its syzygy module.

http://www.mathematik.uni-kassel.de/~izgin/publications.php?lang=en.

A regular normal form is the result of only regular reduction steps until no regular reduction is possible anymore. A regular normal form does not have to be unique as we are, in general, not reducing regular with respect to a Gröbner basis in the v-part.

This means that no more involutively regular reduction steps are possible.

This notion of a strong L-basis is not related to strong or weak involutive bases. However, it can be shown, that from a strong L-basis, two weak involutive bases will arise (see [11, Prop. 4.3.3], whose proof can easily be adapted to a general involutive division L).

This means, that the set of v-parts of G does not contain two elements \(v_1,v_2\) such that \({{\,\mathrm{lt}\,}}(v_1)\mid _{L,B_v}{{\,\mathrm{lt}\,}}(v_2)\).

In this work, every variable with an index smaller or equal to the class of a term \(t'\), written cls\((t'){:}{=}\min \{r: x_r\mid t'\}\), is Pommaret multiplicative for \(t'\).

This means, that there is no element in G that can be involtuively regular reduced by G.

Here, we do not want to discuss if it is even finished up to elements with signature \({{\,\mathrm{lt}\,}}(\varvec{u})\).

Remember that we are only interested in a strong P-basis for \(\prec _1=\prec _\text {degrevlex}\).

Remember that q is an upper bound, or the Castelnuovo–Mumford regularity.

Otherwise the algorithm would have computed Syz(F) and \({{\,\mathrm{lt}\,}}(\varvec{u}')\) could not be involutively irreducible by Syz(F).

Here, we mean the common notion of involutive reducibility without any restrictions by a u-part.

This lemma is an involutive variant of a claim embedded in Theorem 3.1 from [6].

We will introduce it in Sect. 4.

Also, we will discuss later in this remark how to deal with an error message for Syz(F) coming from the Pommaret version of the algorithm.

For the argument corresponding to Syz(F), one may look up the arguments in the proof of correctness of the (fully) involutive GVW algorithm.

This is a property of the Janet division [18, p. 67].

This means that in its current form the implementation is not yet optimised and will have problems with larger examples. The Maple codes of our programs are available at http://www.mathematik.uni-kassel.de/~izgin/publications.php?lang=en.

Remember that we have an index of safety for every coordinate transformation that we perform.

The Maple code is available at http://www.mathematik.uni-kassel.de/~izgin/publications.php?lang=en.

Binaei, B., Hashemi, A., Seiler, W.M.: Computation of Pommaret bases using syzygies. In: Computer Algebra in Scientific Computing. 20th International Workshop, CASC 2018, Lille, France, September 17–21, 2018. Proceedings, pp. 51–66. Springer, Cham (2018)

Buchberger, B.: Ein Algorithmus zum Auffinden der Basiselemente des Restklassenringes nach einem nulldimensionalen Polynomideal. Ph.D. thesis, Universität Innsbruck, 1965. (Engl. translation: J. Symb. Comput. 41 (2006) 475–511)

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

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. ACM Press, New York (2002)

Gao, S., Guan, Y., Volny, F.: A new incremental algorithm for computing Groebner bases. In: Proceedings of the 35th International Symposium on Symbolic and Algebraic Computation, ISSAC 2010, Munich, Germany, July 25–28, 2010, pp. 13–19. Association for Computing Machinery (ACM), New York (2010)

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

Gebauer, R., Möller, H.M.: On an installation of Buchberger’s algorithm. J. Symb. Comput. 6(2–3), 275–286 (1988)MathSciNetCrossRef

Gerdt, V.P.: On the relation between Pommaret and Janet bases. In: Computer Algebra in Scientific Computing. CASC 2000. Proceedings of the 3rd Workshop, Samarkand, Uzbekistan, October 5–9, 2000, pp. 167–181. Springer, Berlin (2000)

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

10.

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

11.

Izgin, T.: The involutive GVW algorithm and the computation of Pommaret bases. Master’s thesis, University of Kassel, Germany (2020)

12.

Janet, M.: Sur les systèmes d’équations aux dérivées partielles. J. Math. Pure Appl. 3, 65–151 (1920)MathSciNetMATH

13.

Lazard, D.: Gröbner bases, Gaussian elimination and resolution of systems of algebraic equations. Computer algebra, EUROCAL ’83, Proceedings Conference, London 1983, Lecture Notes Computer Science 162, pp. 146–156 (1983)

14.

Li, D., Liu, J., Liu, W., Zheng, L.: GVW algorithm over principal ideal domains. J. Syst. Sci. Complex. 26(4), 619–633 (2013)MathSciNetCrossRef

15.

Li, T., Sun, Y., Huang, Z., Wang, D., Lin, D.: Speeding up the GVW algorithm via a substituting method. J. Syst. Sci. Complex. 32(1), 205–233 (2019)MathSciNetCrossRef

16.

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, pp. 320–328. ACM Press, Baltimore (1992)

17.

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, 261–338 (2009)MathSciNetCrossRef

18.

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

19.

Simões, B.: An Hilbert-Driven Strategy for Signature-Based Gröbner Basis Algorithms. In: Future Vision and Trends on Shapes, Geometry and Algebra, pp. 13–37. Springer (2014)

20.

Sun, Y., Huang, Z., Wang, D., Lin, D.: An improvement over the GVW algorithm for inhomogeneous polynomial systems. Finite Fields Appl. 41, 174–192 (2016)MathSciNetCrossRef

21.

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

Titel: An Involutive GVW Algorithm and the Computation of Pommaret Bases
verfasst von: Amir Hashemi
Thomas Izgin
Daniel Robertz
Werner M. Seiler
Publikationsdatum: 07.06.2021
Verlag: Springer International Publishing
Erschienen in: Mathematics in Computer Science / Ausgabe 3/2021
Print ISSN: 1661-8270
Elektronische ISSN: 1661-8289
DOI: https://doi.org/10.1007/s11786-021-00512-5

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 3/2021

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

Creative Telescoping on Multiple Sums

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

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

Foreword, with a Dedication to Vladimir Gerdt

Algorithmic Reduction of Biological Networks with Multiple Time Scales