nach oben

Mathematics in Computer Science

Erschienen in:

21.11.2019

Modular Techniques for Noncommutative Gröbner Bases

verfasst von: Wolfram Decker, Christian Eder, Viktor Levandovskyy, Sharwan K. Tiwari

Erschienen in: Mathematics in Computer Science | Ausgabe 1/2020

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

We extend modular techniques for computing Gröbner bases from the commutative setting to the vast class of noncommutative G-algebras. As in the commutative case, an effective verification test is only known to us in the graded case. In the general case, our algorithm is probabilistic in the sense that the resulting Gröbner basis can only be expected to generate the given ideal, with high probability. We have implemented our algorithm in the computer algebra system Singular and give timings to compare its performance with that of other instances of Buchberger’s algorithm, testing examples from D-module theory as well as classical benchmark examples. A particular feature of the modular algorithm is that it allows parallel runs.

Vorheriger Artikel Vertex Coloring of a Graph for Memory Constrained Scenarios

Nächster Artikel A Different Construction for Some Classes of Quantum MDS Codes

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

“!!” means double factorial.

We have to use a weighted cardinality count: when enlarging \({\mathcal {P}}\), the total weight of the elements already present must be strictly smaller than the total weight of the new elements. Otherwise, though highly unlikely in practical terms, it may happen that only unlucky primes are accumulated.

Andres, D., Brickenstein, M., Levandovskyy, V., Martín-Morales, J., Schönemann, H.: Constructive D-module theory with SINGULAR. Math. Comput. Sci. 4(2–3), 359–383 (2010)MathSciNetCrossRef

Apel, J.: Gröbnerbasen in nichtkommutativen Algebren und ihre Anwendung (Gröbner bases in noncommutative algebras and their applications). Karl-Marx-Univ., Leipzig (1988)

Arnold, E.A.: Modular algorithms for computing Gröbner bases. J. Symb. Comput. 35(4), 403–419 (2003)CrossRef

Bernstein, I.: Modules over a ring of differential operators. Study of the fundamental solutions of equations with constant coefficients. Funct. Anal. Appl. 5, 89–101 (1971)CrossRef

Böhm, J., Decker, W., Fieker, C., Pfister, G.: The use of bad primes in rational reconstruction. Math. Comp. 84(296), 3013–3027 (2015)MathSciNetCrossRef

Bueso, J., Gómez-Torrecillas, J., Lobillo, F.: Re-filtering and exactness of the Gelfand–Kirillov dimension. Bull. Sci. Math. 125(8), 689–715 (2001)MathSciNetCrossRef

Bueso, J., Gómez-Torrecillas, J., Verschoren, A.: Algorithmic Methods in Non-commutative Algebra, Applications to Quantum Groups. Kluwer Academic Publishers, Dordrecht (2003)CrossRef

Castro, F.: Calculs effectifs pour les idéaux d’opérateurs différentiels. (Effective computations for ideals of differential operators). Géométrie algébrique et applications, C. R. 2ième Conf. int., La Rabida/Espagne 1984, III: Géométrie réelle. Systèmes diff́erentielles et théorie de Hodge, Trav. Cours 24, 1–19 (1987)

Ceria, M., Mora, T.: Buchberger–Zacharias theory of multivariate Ore extensions. J. Pure Appl. Algebra 221(12), 2974–3026 (2017)MathSciNetCrossRef

10.

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

11.

Cheng, H., Labahn, G.: Output-sensitive modular algorithms for polynomial matrix normal forms. J. Symb. Comput. 42(7), 733–750 (2007)MathSciNetCrossRef

12.

Decker, W., Greuel, G.-M., Pfister, G., Schönemann, H.: Singular 4-1-2: a computer algebra system for polynomial computations (2019). http://www.singular.uni-kl.de

13.

Ebert, G.: Some comments on the modular approach to Gröbner-bases. SIGSAM Bull. 17(2), 28–32 (1983)CrossRef

14.

García García, J.I., García Miranda, J., Lobillo, F.: Elimination orderings and localization in PBW algebras. Linear Algebra Appl. 430(8–9), 2133–2148 (2009)MathSciNetCrossRef

15.

García Román, M., García Román, S.: Gröbner bases and syzygies on bimodules over PBW algebras. J. Symb. Comput. 40(3), 1039–1052 (2005)CrossRef

16.

Greuel, G.-M., Levandovskyy, V., Motsak, O., Schönemann, H.: Plural. a singular 4-1-2 subsystem for computations with non-commutative polynomial algebras (2019). http://www.singular.uni-kl.de

17.

Idrees, N., Pfister, G., Steidel, S.: Parallelization of modular algorithms. J. Symb. Comput. 46(6), 672–684 (2011)MathSciNetCrossRef

18.

Kandri-Rody, A., Weispfenning, V.: Non-commutative Gröbner bases in algebras of solvable type. J. Symb. Comput. 9(1), 1–26 (1990)CrossRef

19.

Krause, G.R., Lenagan, T.H.: Growth of Algebras and Gelfand–Kirillov Dimension, Revised edn. American Mathematical Society, Providence (2000)MATH

20.

Kredel, H.: Solvable Polynomial Rings. Shaker, Aachen (1993)MATH

21.

Levandovskyy, V.: Non-commutative computer algebra for polynomial algebras: Gröbner bases, applications and implementation. Doctoral thesis, Universität Kaiserslautern (2005)

22.

Levandovskyy, V.: PBW bases, non-degeneracy conditions and applications. In: Representations of Algebras and Related Topics. Proceedings from the 10th International Conference, ICRA X, Toronto, Canada, July 15–August 10, 2002. Dedicated to V. Dlab on the occasion of his 70th birthday, pp. 229–246. American Mathematical Society (AMS), Providence (2005)

23.

Levandovskyy, V., Koutschan, C., Motsak, O.: On two-generated non-commutative algebras subject to the affine relation. In: Gerdt, V., Koepf, W., Mayr, E., Vorozhtsov, E. (eds.) Proceedings of CASC ’2011, Volume 6885 of LNCS, pp. 309–320. Springer, Berlin (2011)

24.

Levandovskyy, V., Schönemann, H.: Plural: a computer algebra system for noncommutative polynomial algebras. In: Proceedings of the 2003 International Symposium on Symbolic and Algebraic Computation, ISSAC 2003, Philadelphia, PA, USA, August 3–6, 2003, pp. 176–183. ACM Press, New York (2003)

25.

Li, H.: Noncommutative Gröbner bases and filtered-graded transfer. Lecture Notes in Mathematics, vol. 1795. Springer, Berlin (2002)

26.

Mora, T.: An introduction to commutative and noncommutative Gröbner bases. Theor. Comput. Sci. 134(1), 131–173 (1994)CrossRef

27.

Noro, M.: An efficient modular algorithm for computing the global \(b\)-function. In: Cohen, A.M., Gao, X.-S., Takayama, N. (eds.) Mathematical Software (Beijing, 2002), pp. 147–157. World Sci. Publ, River Edge (2002)CrossRef

28.

Noro, M., Yokoyama, K.: Usage of modular techniques for efficient computation of ideal operations. Math. Comput. Sci. 12(1), 1–32 (2018) MathSciNetCrossRef

29.

Pritchard, F.L.: The ideal membership problem in non-commutative polynomial rings. J. Symb. Comput. 22(1), 27–48 (1996)MathSciNetCrossRef

30.

Reiffen, H.-J.: Das Lemma von Poincaré für holomorphe Differentialformen auf komplexen Räumen. Math. Z. 101, 269–284 (1967)MathSciNetCrossRef

31.

Sabbah, C.: Proximité évanescente I. La structure polaire d’un D-Module. Compos. Math. 62(3), 283–328 (1987)MATH

32.

Takayama, N.: Gröbner basis and the problem of contiguous relations. Japan J. Appl. Math. 6(1), 147–160 (1989)MathSciNetCrossRef

33.

The SymbolicData Project (2019). https://symbolicdata.github.io

34.

Weispfenning, V.: Finite Gröbner bases in non-noetherian skew polynomial rings. In: Proceedings of ISSAC’92, pp. 329–334. ACM Press, New York (1992)

Titel: Modular Techniques for Noncommutative Gröbner Bases
verfasst von: Wolfram Decker
Christian Eder
Viktor Levandovskyy
Sharwan K. Tiwari
Publikationsdatum: 21.11.2019
Verlag: Springer International Publishing
Erschienen in: Mathematics in Computer Science / Ausgabe 1/2020
Print ISSN: 1661-8270
Elektronische ISSN: 1661-8289
DOI: https://doi.org/10.1007/s11786-019-00412-9

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 1/2020

A Signature Based Border Basis Algorithm

A Different Construction for Some Classes of Quantum MDS Codes

Coxeter Triangulations Have Good Quality

The Depth of Compositions

On the Extension of Adams–Bashforth–Moulton Methods for Numerical Integration of Delay Differential Equations and Application to the Moon’s Orbit

Nori Diagrams and Persistent Homology

Premium Partner