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.
Type de document :
Communication dans un congrès
Erich Kaltofen, Gilles Villard. International Conference on Symbolic and Algebraic Computation, Jul 2001, London, Ontario, Canada. ACM, pp.323-331, 2001, Proceedings of the 2001 international symposium on Symbolic and algebraic computation. 〈10.1145/384101.384145〉
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00517999
Contributeur : Emmanuel Thomé <>
Soumis le : jeudi 16 septembre 2010 - 10:45:44
Dernière modification le : jeudi 11 janvier 2018 - 06:19:44
Document(s) archivé(s) le : vendredi 17 décembre 2010 - 02:47:23

Fichier

fastbw.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Emmanuel Thomé. Fast computation of linear generators for matrix sequences and application to the block Wiedemann algorithm. Erich Kaltofen, Gilles Villard. International Conference on Symbolic and Algebraic Computation, Jul 2001, London, Ontario, Canada. ACM, pp.323-331, 2001, Proceedings of the 2001 international symposium on Symbolic and algebraic computation. 〈10.1145/384101.384145〉. 〈inria-00517999〉

Partager

Métriques

Consultations de la notice

189

Téléchargements de fichiers

81