Skip to main content
main-content
Top

Hint

Swipe to navigate through the articles of this issue

06-06-2019 | Original Paper | Issue 6/2019

Applicable Algebra in Engineering, Communication and Computing 6/2019

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

Journal:
Applicable Algebra in Engineering, Communication and Computing > Issue 6/2019
Authors:
Joris van der Hoeven, Robin Larrieu
Important notes

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

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 ABP. 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.

Please log in to get access to this content

To get access to this content you need the following product:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

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

  • über 69.000 Bücher
  • über 500 Zeitschriften

aus folgenden Fachgebieten:

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

Testen Sie jetzt 30 Tage kostenlos.

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 58.000 Bücher
  • über 300 Zeitschriften

aus folgenden Fachgebieten:

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




Testen Sie jetzt 30 Tage kostenlos.

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 50.000 Bücher
  • über 380 Zeitschriften

aus folgenden Fachgebieten:

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




Testen Sie jetzt 30 Tage kostenlos.

Literature
About this article

Premium Partner

    Image Credits