Skip to Main content Skip to Navigation
Conference papers

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

Pascal Giorgi 1 Romain Lebreton 1
1 ECO - Exact Computing
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.
Document type :
Conference papers
Complete list of metadatas

Cited literature [24 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01232873
Contributor : Pascal Giorgi <>
Submitted on : Tuesday, November 24, 2015 - 11:57:00 AM
Last modification on : Tuesday, June 18, 2019 - 3:26:10 PM
Document(s) archivé(s) le : Friday, April 28, 2017 - 2:32:11 PM

File

report-GioLeb.pdf
Files produced by the author(s)

Identifiers

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. pp.202-209, ⟨10.1145/2608628.2608647⟩. ⟨lirmm-01232873⟩

Share

Metrics

Record views

331

Files downloads

497