Online order basis algorithm and its impact on the block Wiedemann algorithm

Pascal Giorgi 1 Romain Lebreton 2, 1
1 ECO - Exact Computing
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
2 ARITH - Arithmétique informatique
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : Order bases are a fundamental tool for linear algebra with polynomial coefficients. In particular, block Wiedemann methods are nowadays able to tackle large sparse matrix problems because they benefit from fast order basis algorithms. However, such fast algorithms suffer from two practical drawbacks: they are not designed for early termination and often require more knowledge on the input than necessary. In this paper, we propose an online algorithm for order basis which allows for both early termination and minimal input requirement while keeping quasi-optimal complexity in the order. Using this algorithm inside block Wiedemann methods leads to an improvement of their practical performance by a constant factor.
Type de document :
Communication dans un congrès
ISSAC: International Symposium on Symbolic and Algebraic Computation, Jul 2014, Kobe, Japan. ACM, pp.202-209, 2014, Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation. 〈http://dl.acm.org/citation.cfm?id=2608628&coll=DL&dl=GUIDE&CFID=732905570&CFTOKEN=40081280〉. 〈10.1145/2608628.2608647〉
Liste complète des métadonnées

Littérature citée [24 références]  Voir  Masquer  Télécharger

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01232873
Contributeur : Pascal Giorgi <>
Soumis le : mardi 24 novembre 2015 - 11:57:00
Dernière modification le : jeudi 11 janvier 2018 - 06:27:05
Document(s) archivé(s) le : vendredi 28 avril 2017 - 14:32:11

Fichier

report-GioLeb.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Pascal Giorgi, Romain Lebreton. Online order basis algorithm and its impact on the block Wiedemann algorithm. ISSAC: International Symposium on Symbolic and Algebraic Computation, Jul 2014, Kobe, Japan. ACM, pp.202-209, 2014, Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation. 〈http://dl.acm.org/citation.cfm?id=2608628&coll=DL&dl=GUIDE&CFID=732905570&CFTOKEN=40081280〉. 〈10.1145/2608628.2608647〉. 〈lirmm-01232873〉

Partager

Métriques

Consultations de la notice

101

Téléchargements de fichiers

149