Signature Rewriting in Gröbner Basis Computation

Christian Eder 1 Bjarke Hammersholt Roune 2
1 PolSys - Polynomial Systems
LIP6 - Laboratoire d'Informatique de Paris 6, Inria Paris-Rocquencourt
2 Fachbereich Mathematik [Kaiserslautern]
Abstract : We introduce the RB algorithm for Gro ̈bner basis compu- tation, a simpler yet equivalent algorithm to F5GEN. RB contains the original unmodified F5 algorithm as a special case, so it is possible to study and understand F5 by con- sidering the simpler RB. We present simple yet complete proofs of this fact and of F5's termination and correctness. RB is parametrized by a rewrite order and it contains many published algorithms as special cases, including SB. We prove that SB is the best possible instantiation of RB in the following sense. Let X be any instantiation of RB (such as F5). Then the S-pairs reduced by SB are always a subset of the S-pairs reduced by X and the basis computed by SB is always a subset of the basis computed by X.
Type de document :
Communication dans un congrès
Kauers, Manuel. ISSAC 2013 - International Symposium on Symbolic and Algebraic Computation, Jun 2013, Boston, United States. ACM, pp.331-338, 2013, 〈10.1145/2465506.2465522〉
Liste complète des métadonnées

Littérature citée [11 références]  Voir  Masquer  Télécharger
https://hal.inria.fr/hal-00930273
Contributeur : Elias Tsigaridas <>
Soumis le : mardi 14 janvier 2014 - 15:32:55
Dernière modification le : jeudi 22 novembre 2018 - 14:40:44
Document(s) archivé(s) le : mardi 15 avril 2014 - 16:25:53

Fichier

sbff.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

INRIA | UPMC | LIP6 | INRIA-ROCQ | SORBONNE-UNIVERSITE

Citation

Christian Eder, Bjarke Hammersholt Roune. Signature Rewriting in Gröbner Basis Computation. Kauers, Manuel. ISSAC 2013 - International Symposium on Symbolic and Algebraic Computation, Jun 2013, Boston, United States. ACM, pp.331-338, 2013, 〈10.1145/2465506.2465522〉. 〈hal-00930273〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

167

Téléchargements de fichiers

293

Contact


archive-ouverte@inria.fr