Online order basis algorithm and its impact on the block Wiedemann algorithm - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Conference Papers Year : 2014

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

Pascal Giorgi
Romain Lebreton

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.
Fichier principal
Vignette du fichier
report-GioLeb.pdf (604.85 Ko) Télécharger le fichier
Origin Files produced by the author(s)
Loading...

Dates and versions

lirmm-01232873 , version 1 (24-11-2015)

Identifiers

Cite

Pascal Giorgi, Romain Lebreton. Online order basis algorithm and its impact on the block Wiedemann algorithm. ISSAC 204 - 39th International Symposium on Symbolic and Algebraic Computation, Jul 2014, Kobe, Japan. pp.202-209, ⟨10.1145/2608628.2608647⟩. ⟨lirmm-01232873⟩
208 View
347 Download

Altmetric

Share

Gmail Mastodon Facebook X LinkedIn More