Fast computation of linear generators for matrix sequences and application to the block Wiedemann algorithm - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2001

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

Résumé

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.
Fichier principal
Vignette du fichier
fastbw.pdf (163.41 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

inria-00517999 , version 1 (16-09-2010)

Identifiants

Citer

Emmanuel Thomé. Fast computation of linear generators for matrix sequences and application to the block Wiedemann algorithm. ISSAC '01: Proceedings of the 2001 international symposium on Symbolic and algebraic computation, Jul 2001, London, Ontario, Canada. pp.323-331, ⟨10.1145/384101.384145⟩. ⟨inria-00517999⟩
365 Consultations
346 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More