Fast computation of linear generators for matrix sequences and application to the block Wiedemann algorithm

Abstract : In this paper we describe how the half-gcd algorithm can be adapted in order to speed up the sequential stage of Coppersmith's block Wiedemann algorithm for solving large sparse linear systems over any finite field. This very stage solves a sub-problem than can be seen as the computation of a linear generator for a matrix sequence. Our primary realm of interest is the field GF(q) for large prime power q. For the solution of a N * N system, the complexity of this sequential part drops from O(N²) to O(M(N)log(N)) where M(d) is the cost for multiplying two polynomials of degree d. We discuss the implications of this improvement for the overall cost of the block Wiedemann algorithm and how its parameters should be chosen for best efficiency.
Complete list of metadatas

Cited literature [25 references]  Display  Hide  Download

https://hal.inria.fr/inria-00517999
Contributor : Emmanuel Thomé <>
Submitted on : Thursday, September 16, 2010 - 10:45:44 AM
Last modification on : Wednesday, March 27, 2019 - 4:41:26 PM
Long-term archiving on: Friday, December 17, 2010 - 2:47:23 AM

File

fastbw.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Emmanuel Thomé. Fast computation of linear generators for matrix sequences and application to the block Wiedemann algorithm. International Conference on Symbolic and Algebraic Computation, Jul 2001, London, Ontario, Canada. pp.323-331, ⟨10.1145/384101.384145⟩. ⟨inria-00517999⟩

Share

Metrics

Record views

420

Files downloads

279