GBLA – Gröbner Basis Linear Algebra Package

Brice Boyer 1 Christian Eder 2 Jean-Charles Faugère 1 Sylvian Lachartre 3 Fayssal Martani 1
1 PolSys - Polynomial Systems
LIP6 - Laboratoire d'Informatique de Paris 6, Inria de Paris
2 Fachbereich Mathematik [Kaiserslautern]
3 THALES
Abstract : This is a system paper about a new GPLv2 open source C library GBLA implementing and improving the idea [7] of Faugère and Lachartre (GB reduction). We further exploit underlying structures in matrices generated during Gröbner basis computations in algorithms like F4 or F5 taking advantage of block patterns by using a special data structure called multilines. Moreover, we discuss a new order of operations for the reduction process. In various different experimental results we show that GBLA performs better than GB reduction or Magma in sequential computations (up to 40% faster) and scales much better than GB reduction for a higher number of cores: On 32 cores we reach a scaling of up to 26. GBLA is up to 7 times faster than GB reduction. Further, we compare different parallel schedulers GBLA can be used with. We also developed a new advanced storage format that exploits the fact that our matrices are coming from Gröbner basis computations, shrinking storage by a factor of up to 4. A huge database of our matrices is freely available with GBLA.
Keywords : Linear algebra Gr\obner basis
Type de document :
Communication dans un congrès
41st International Symposium on Symbolic and Algebraic Computation, Jul 2016, Waterloo, ON, Canada. pp.135-142, 2016, 〈10.1145/2930889.2930914〉
Liste complète des métadonnées

Littérature citée [12 références]  Voir  Masquer  Télécharger
https://hal.inria.fr/hal-01276346
Contributeur : Jean-Charles Faugère <>
Soumis le : mardi 22 novembre 2016 - 17:06:34
Dernière modification le : jeudi 22 novembre 2018 - 14:24:54
Document(s) archivé(s) le : lundi 20 mars 2017 - 18:06:16

Fichier

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

Identifiants

Collections

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

Citation

Brice Boyer, Christian Eder, Jean-Charles Faugère, Sylvian Lachartre, Fayssal Martani. GBLA – Gröbner Basis Linear Algebra Package. 41st International Symposium on Symbolic and Algebraic Computation, Jul 2016, Waterloo, ON, Canada. pp.135-142, 2016, 〈10.1145/2930889.2930914〉. 〈hal-01276346v2〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

310

Téléchargements de fichiers

73

Contact


archive-ouverte@inria.fr