nach oben

Mathematics in Computer Science

Erschienen in:

01.12.2022

Applications of Bar Code to Involutive Divisions and a “Greedy” Algorithm for Complete Sets

verfasst von: Michela Ceria

Erschienen in: Mathematics in Computer Science | Ausgabe 4/2022

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

Given a finite set of terms U in n variables, we describe an algorithm which finds – if it exists – an ordering on the variables such that U is a complete set according to Janet involutive division. The algorithm, based on Bar Codes for monomial ideals, is able to adjust the variables ordering with a sort of backtracking technique, thus allowing to find the desired ordering without trying all the n! possible ones.

Vorheriger Artikel Recurrences for Quadrilateral High-Order Finite Elements

Nächster Artikel De Nugis Groebnerialium 7: Janet, Gerdt, Tamari

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

Nur mit Berechtigung zugänglich

In this paper, the ordering on the variables will be fundamental. Unless otherwise specified we will consider \(x_1<\ldots <x_n\).

An alternative construction has been given in detail in [5].

If a term \(\pi ^i(t_{{\overline{j}}})\) presents no repetition in \({\overline{M}}^{[i]}\), the sublist containing it will contain only that term, so \(h=0\).

In [6, 7] a set of terms is constructed with an analogous procedure; the paper [10] links this set to Pommaret bases [40, 41].

The use of the word “greedy” is actually not the Computer Theoretic one, we only intend that we try to make choices that try to decrease the number of tests.

Remember that the last row of a Bar Code, namely that on the bottom, is the row associated to the maximal variable (see Sect. 2.2).

Cartan, E.: Sur l’intégration des systèmes d’équations aux différentielles totals. Ann. Éc. Norm. \(3^e\) série 18, 241, (1901)

Cartan, E.: Sur la structure des groupes infinis de transformations. Ann. Éc. Norm. \(3^e\) série 21, 153, (1904)

Cartan, E.: Sur les systèmes en involution d’équations aux dérivées partielles du second ordre à une fonction inconnue de trois variables indépendentes. Bull. Soc. Marth. 39, 356 (1920)

Ceria, M.: A proof of the “Axis of Evil theorem” for distinct points. Rendiconti del Seminario Matematico dell’Università e del Politecnico di Torino 72(3–4), 213–233 (2014)

Ceria, M.: Bar Code for monomial ideals. J. Symbol. Comput. (2019). https://doi.org/10.1016/j.jsc.2018.06.012 J. Symbol. Comput., Vol 91: 30-56

Ceria, M.: Bar code: a visual representation for finite set of terms and its applications. Math. Comput. Sci. 14(2), 497-513 (2020)

Ceria, M.: Bar code versus janet tree, Atti dell’Accademia Peloritana dei Pericolanti, Vol 97, No 2 (2019)

Ceria, M.: Bar Code and Janet-like division, Atti dell’Accademia Peloritana dei Pericolanti, Classe di Scienze Fisiche, Matematiche e Naturali, Vol.100 N.1 https://doi.org/10.1478/AAPP.1001A2

Ceria, M., Mora, T.: Combinatorics of ideals of points: a Cerlienco-Mureddu-like approach for an iterative lex game, arXiv:1805.09165

10.

Ceria, M., Mora, T., Roggero, M.: Term-ordering free involutive bases, https://doi.org/10.1016/j.jsc.2014.09.005. J. Symbol. Comput. (2015)

11.

Ceria, M., Mora, T., Visconti, A.: Degroebnerization and its applications: a new approach for data modelling, preprint

12.

Cerlienco, L., Mureddu, M.: Algoritmi combinatori per l’interpolazione polinomiale in dimensione \(\ge 2\), Publ. I.R.M.A. Strasbourg, 461/S-24 Actes \(24^e\) Séminaire Lotharingien, p.39-76 (1993)

13.

Cerlienco, L., Mureddu, M.: From algebraic sets to monomial linear bases by means of combinatorial algorithms. Discrete Math. 139, 73–87 (1995)MathSciNetCrossRefMATH

14.

Cerlienco, L., Mureddu, M.: Multivariate interpolation and standard bases for macaulay modules. J. Algebra 251, 686–726 (2002)MathSciNetCrossRefMATH

15.

Delassus, E.: Extension du théorème de Cauchy aux systèmes les plus généraux d’équations aux dérivées partielles. Ann. Éc. Norm. \(3^e\) série 13, 421–467 (1896)

16.

Delassus, E.: Sur les systèmes algébriques et leurs relations avec certains systèmes d’equations aux dérivées partielles. Ann. Éc. Norm. \(3^e\) série 14, 21–44 (1897)

17.

Delassus, E.: Sur les invariants des systèmes différentiels. Ann. Éc. Norm. \(3^e\) série 25 255–318, (1908)

18.

Eisenbud, D.: Commutative Algebra: with a View Toward Algebraic Geometry. Springer, USA (2013)MATH

19.

Felszeghy, B., Ráth, B., Rónyai, L.: The lex game and some applications. J. Symbolic Comput. 41, 663–681 (2006)MathSciNetCrossRefMATH

20.

Galligo, A.: A propos du théorem de préparation de Weierstrass, L. N. Math.40, Springer, 543–579, (1974)

21.

Gerdt, V.P., Blinkov, Y.A.: Involutive bases of Polynomial ideals. Math. Comp. Sim. 45, 543–560 (1998)MathSciNetCrossRefMATH

22.

Gerdt, V.P., Blinkov, Y.A.: Minimal involutive bases. Math. Comp. Sim. 45, 519–541 (1998)MathSciNetCrossRefMATH

23.

Gerdt, V.P., Blinkov, Y.A.: Involutive Division Generated by an Antigraded Monomial Ordering L. N. Comp. Sci 6885, Springer, 158-174, (2011)

24.

Gerdt, V.P., Blinkov, Y.A.: Janet-like monomial division. International workshop on computer algebra in scientific computing, Springer, 174–183, (2005)

25.

Gerdt, V.P., Blinkov, Y.A.: Janet-like Gröbner bases, international workshop on computer algebra in scientific computing, Springer, 184–195, (2005)

26.

Gerdt, V., Blinkov, Y., Yanovich, D.: Construction of Janet bases I. Monomial bases, in Computer Algebra in Scientific Computing CASC, 233-247 (2001)

27.

Grauert, H.: Über die Deformation isolierter Singularitäten analytischer Mengen. Inventiones mathematicae 15, 171-198, (1971/72)

28.

Green, M., Stillman, M.: A tutorial on generic initial ideals. In: Buchberger, B., Winkler, F. (eds.) Groebner Bases Appl., pp. 90–108. Press, Cambridge Univ (1998)CrossRef

29.

Gunther, N.: Sur la forme canonique des systèmes déquations homogènes (in russian) [Journal de l’Institut des Ponts et Chaussées de Russie] Izdanie Inst. Inz̆. Putej Soobs̆c̆enija Imp. Al. I. 84, (1913)

30.

Gunther, N.: Sur la forme canonique des equations algébriques C.R. Acad. Sci. Paris 157, 577–80 (1913)

31.

Gunther, N.: Sur les modules des formes algébriques Trudy Tbilis. Mat. Inst. 9, 97–206 (1941)MathSciNet

32.

Herzog, J.: A survey on stanley depth. In monomial ideals, computations and applications, Springer, Berlin, Heidelberg 3-45, (2013)

33.

Hironaka, H.: Idealistic exponents of singularity In: Algebraic Geometry, The Johns Hopkins Centennial Lectures. 52-125 (1977)

34.

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

35.

Janet, M.: Les modules de formes algébriques et la théorie générale des systemes différentiels, Annales scientifiques de l’École Normale Supérieure, (1924)

36.

Janet, M.: Les systèmes d’équations aux dérivées partelles, Gauthier-Villars, (1927)

37.

Janet, M.: Lecons sur les systèmes d’équations aux dérivées partelles , Gauthier-Villars (1929)

38.

Mora, T.: Solving Polynomial Equation Systems. 4 Vols., Cambridge University Press, I (2003), II (2005), III (2015), IV (2016)

39.

Mumford, D.: Lectures on Curves on an Algebraic Surface. Princeton Univ. Press (1966)

40.

Pommaret, J. F.: Systems of partial differential equations and Lie pseudogroups, Gordon and Brach (1978)

41.

Pommaret, J.F., Akli, H.: Effective methods for systems of algebraic partial differential equations, Progress in Mathematics 94, 411–426, Birkhäuser, (1990)

42.

Riquier, C.: Les systèmes d’équations aux dérivées partielles, Gauthiers-Villars, (1910)

43.

Robinson, L.B.: A new canonical form for systems of partial differential equations. Am. J. Math. 39, 95–112 (1917)MathSciNetCrossRefMATH

44.

Robinson, L.B.: Sur les systémes d’équations aux dérivées partialles C.R. Acad. Sci. Paris 157, 106–108, (1913)

45.

Seiler, W.M.: Involution: The Formal Theory of Differential Equations and its Applications in Computer Algebra, Vol.24, Springer Science & Business Media, (2009)

Titel: Applications of Bar Code to Involutive Divisions and a “Greedy” Algorithm for Complete Sets
verfasst von: Michela Ceria
Publikationsdatum: 01.12.2022
Verlag: Springer International Publishing
Erschienen in: Mathematics in Computer Science / Ausgabe 4/2022
Print ISSN: 1661-8270
Elektronische ISSN: 1661-8289
DOI: https://doi.org/10.1007/s11786-022-00548-1

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 4/2022

30 Years with Vladimir Gerdt

De Nugis Groebnerialium 7: Janet, Gerdt, Tamari

SMS Nanning and RWTH Aachen: In Memory of Vladimir Gerdt

How Many Structure Constants do Exist in Riemannian Geometry?

Personal Recollections of Prof. Vladimir P. Gerdt

Memories of Vladimir Gerdt

Premium Partner