nach oben

Mathematics in Computer Science

Erschienen in:

11.02.2020

A Signature Based Border Basis Algorithm

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

The Border Basis Algorithm (BBA) still suffers from the lack of analogues of Buchberger’s criteria for avoiding unnecessary reductions. In this paper we develop a signature based technique which provides a first remedial step: signature bounds allow us to recognize multiple reductions of the same ancestor polynomial. The new signature based algorithm is then combined with the Boolean BBA for ideals of Boolean polynomials. Experiments show that it is at least 5 times faster than the standard Boolean BBA.

Vorheriger Artikel Coxeter Triangulations Have Good Quality

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

Buchberger, B.: Bruno Buchberger’s Ph.D. thesis 1965: an algorithm for finding the basis elements of the residue class ring of a zero dimensional polynomial ideal. J. Symb. Comput. 41, 475–511 (2006)CrossRef

Faugère, J.-C.: A new efficient algorithm for computing Gröbner bases without reduction to zero (F5). In: Proc. Conf. ISSAC 2002, pp. 75–83. ACM Press, New York (2002)

Eder, C., Faugère, J.-C.: A survey on signature-based algorithms for computing Gröbner bases. J. Symb. Comput. 80, 719–784 (2017)CrossRef

Mourrain, B.: A new criterion for normal form algorithms. In: Fossorier, M., Imai, H., Lin, S., Poli, A. (eds.) Proc. Conf. AAECC-13, Honolulu 1999, LNCS, Vol. 1719, pp. 440–443. Springer, Heidelberg (1999)

Kehrein, A., Kreuzer, M.: Computing border bases. J. Pure Appl. Alg. 205, 279–295 (2006)MathSciNetCrossRef

Horacek, J., Kreuzer, M., Messeng Ekossono, A.-S.: Computing Boolean border bases. In: Proc. Conf. SYNASC’16, Timisoara 2016. IEEE. www.sc-square.org/CSA/workshop1-papers/paper3.pdf

Mourrain, B., Trébuchet, P.: Generalized normal forms and polynomial system solving. In: Proc. Conf. ISSAC’05, Beijing 2005, pp. 253-260. ACM Press, New York (2005)

Kaspar, S.: Computing border bases without using a term ordering. Beitr. Algebra Geom. 54, 211–223 (2013)MathSciNetCrossRef

The ApCoCoA Team, ApCoCoA: Applied Computations in Computer Algebra. http://apcocoa.uni-passau.de

10.

Kreuzer, M., Robbiano, L.: Computational Commutative Algebra 1. Springer, Heidelberg (2000)CrossRef

11.

Kreuzer, M., Robbiano, L.: Computational Commutative Algebra 2. Springer, Heidelberg (2005)MATH

12.

Gay, M., Burchard, J., Horacek, J., Messeng Ekossono, A.-S., Schubert, T., Becker, B., Kreuzer, M., Polian, I.: Small scale AES toolbox: algebraic and propositional formulas, circuit-implementations and fault equations. In: Proc. Conf. Trustworthy Manufacturing and Utilization of Secure Devices (TRUDEVICE 2016), Barcelona, 2016. http://upcommons.upc.edu/handle/2117/99210

13.

SageMath, the Sage Mathematics Software System (Version 7.5.1), The Sage Developers (2017). http://www.sagemath.org

14.

Brickenstein, M., Dreyer, A.: PolyBoRi: a framework for Gröbner basis computations with Boolean polynomials. J. Symb. Comput. 44, 1326–1345 (2009)CrossRef

15.

Soos, M.: The CryptoMiniSat 5 set of solvers at SAT Competition 2016. In: Baljo, T., Heule, M.J.H., Järvisalo, M. (eds.) Proc. SAT COMPETITION 2016, p. 28. University of Helsinki, Helsinki (2016)

Titel: A Signature Based Border Basis Algorithm
Publikationsdatum: 11.02.2020
Erschienen in: Mathematics in Computer Science / Ausgabe 1/2020
Print ISSN: 1661-8270
Elektronische ISSN: 1661-8289
DOI: https://doi.org/10.1007/s11786-020-00459-z

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

The Depth of Compositions

Testing Hyperbolicity of Real Polynomials

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

Modular Techniques for Noncommutative Gröbner Bases

Vertex Coloring of a Graph for Memory Constrained Scenarios

Exploring the Isoptics of Fermat Curves in the Affine Plane Using DGS and CAS