Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Applicable Algebra in Engineering, Communication and Computing
Erschienen in: Applicable Algebra in Engineering, Communication and Computing 6/2019

06.06.2019 | Original Paper

Fast Gröbner basis computation and polynomial reduction for generic bivariate ideals

Erschienen in: Applicable Algebra in Engineering, Communication and Computing | Ausgabe 6/2019

Einloggen

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

search-config
loading …

Abstract

Let \(A, B \in \mathbb {K} [X, Y]\) be two bivariate polynomials over an effective field \(\mathbb {K}\), and let G be the reduced Gröbner basis of the ideal \(I :=\langle A, B \rangle \) generated by A and B with respect to the usual degree lexicographic order. Assuming A and B sufficiently generic, we design a quasi-optimal algorithm for the reduction of \(P \in \mathbb {K} [X, Y]\) modulo G, where “quasi-optimal” is meant in terms of the size of the input A, B, P. Immediate applications are an ideal membership test and a multiplication algorithm for the quotient algebra \(\mathbb {A} :=\mathbb {K} [X, Y] / \langle A, B \rangle \), both in quasi-linear time. Moreover, we show that G itself can be computed in quasi-linear time with respect to the output size.
Vorheriger Artikel On the annihilator ideal of an inverse form: addendum

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
Fußnoten
1
The results from [18] actually apply for more general types of supports, but this will not be needed in this paper.
 
Literatur
1.
Bardet, M., Faugère, J.-C., Salvy, B.: On the complexity of the F5 Gröbner basis algorithm. J. Symb. Comput. 70, 1–24 (2014)MATH
2.
Becker, T., Weispfenning, V.: Gröbner bases: a computational approach to commutative algebra. In: Axler, S., Gehring, F.W., Ribet, K.A. (eds.) Graduate Texts in Mathematics, vol. 141. Springer, New York (1993)CrossRef
3.
Buchberger, B.: Ein Algorithmus zum Auffinden der Basiselemente des Restklassenrings nach einem nulldimensionalen Polynomideal. Ph.D. Thesis, Universitat Innsbruck, Austria (1965)
4.
Cantor, D.G., Kaltofen, E.: On fast multiplication of polynomials over arbitrary algebras. Acta Inf. 28(7), 693–701 (1991)MathSciNetCrossRef
5.
Faugère, J.-C.: A new efficient algorithm for computing Gröbner bases (F4). J. Pure Appl. Algebra 139(1–3), 61–88 (1999)MathSciNetCrossRef
6.
Faugère, J.-C.: A new efficient algorithm for computing Gröbner bases without reduction to zero (F5). In: Proceedings of the 2002 International Symposium on Symbolic and Algebraic Computation, ISSAC’02, pp. 75–83. ACM, New York (2002)
7.
Faugère, J.-C., Gaudry, P., Huot, L., Renault, G.: Polynomial systems solving by fast linear algebra. arXiv:​1304.​6039 (2013)
8.
Faugère, J.-C., Gianni, P., Lazard, D., Mora, T.: Efficient computation of zero-dimensional Gröbner bases by change of ordering. J. Symb. Comput. 16(4), 329–344 (1993)CrossRef
9.
Fischer, M.J., Stockmeyer, L.J.: Fast on-line integer multiplication. In: Proceedings of the 5th ACM Symposium on Theory of Computing, vol. 9, pp. 67–72 (1974)
10.
Fröberg, R., Hollman, J.: Hilbert series for ideals generated by generic forms. J. Symb. Comput. 17(2), 149–157 (1994)MathSciNetCrossRef
11.
Galligo, A.: A propos du théoreme de préparation de Weierstrass. In: Norguet, F. (ed.) Fonctions de plusieurs Variables Complexes, pp. 543–579. Springer, Berlin (1974)
12.
von zur Gathen, J., Gerhard, J.: Modern Computer Algebra, 3rd edn. Cambridge University Press, Cambridge (2013)
13.
Gerdt, V.P., Blinkov, Y.A.: Involutive bases of polynomial ideals. Math. Comput. Simul. 45(5), 519–541 (1998)MathSciNetCrossRef
14.
15.
Harvey, D., van der Hoeven, J., Lecerf, G.: Faster polynomial multiplication over finite fields. J. ACM 63(6), 52 (2017)MathSciNetCrossRef
16.
17.
van der Hoeven, J.: Faster relaxed multiplication. In: Proceeding of the ISSAC’14, pp. 405–412, Kobe (July 2014)
18.
van der Hoeven, J.: On the complexity of polynomial reduction. In: Kotsireas, I., Martínez-Moro, E. (eds.) Proceeding of the Applications of Computer Algebra 2015, Volume 198 of Springer Proceedings in Mathematics and Statistics, pp. 447–458. Springer, Cham (2015)
19.
van der Hoeven, J., Larrieu, R.: Fast reduction of bivariate polynomials with respect to sufficiently regular Gröbner bases. In: Kauers, M., Ovchinnikov, A., Schost, É. (eds.) Proceeding of the ISSAC’18, pp. 199–206. ACM, New York (2018)
20.
21.
Lebreton, R., Schost, E., Mehrabi, E.: On the complexity of solving bivariate systems: the case of non-singular solutions. In: ISSAC: International Symposium on Symbolic and Algebraic Computation, pp. 251–258, Boston (June 2013)
22.
Mayr, E.: Membership in polynomial ideals over \(Q\) is exponential space complete. STACS 89, 400–406 (1989)MathSciNet
23.
Moreno-Socías, G.: Degrevlex Gröbner bases of generic complete intersections. J. Pure Appl. Algebra 180(3), 263–283 (2003)MathSciNetCrossRef
24.
Schönhage, A.: Schnelle Multiplikation von Polynomen über Körpern der Charakteristik 2. Acta Inf. 7, 395–398 (1977)CrossRef
25.
26.
Metadaten
Titel
Fast Gröbner basis computation and polynomial reduction for generic bivariate ideals
Publikationsdatum
06.06.2019
Erschienen in
Applicable Algebra in Engineering, Communication and Computing / Ausgabe 6/2019
Print ISSN: 0938-1279
Elektronische ISSN: 1432-0622
DOI
https://doi.org/10.1007/s00200-019-00389-9