Sparse Gaussian Elimination modulo p: an Update

Bouillaguet, Charles; Delaplace, Claire

Document type :

Communication dans un congrès avec actes

Title :

Sparse Gaussian Elimination modulo p: an Update

Author(s) :

Bouillaguet, Charles [Auteur]

Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 [CRIStAL]
Université de Lille
Delaplace, Claire [Auteur]
Institut de Recherche en Informatique et Systèmes Aléatoires [IRISA]
Université de Rennes [UR]

Conference title :

Computer Algebra in Scientific Computing

City :

Bucharest

Country :

Roumanie

Start date of the conference :

2016-09-19

Book title :

CASC'16

Publication date :

2016-06-19

HAL domain(s) :

Informatique [cs]/Logiciel mathématique [cs.MS]

English abstract : [en]

This paper considers elimination algorithms for sparse matrices over finite fields. We mostly focus on computing the rank, because it raises the same challenges as solving linear systems, while being slightly simpler. We ...
Show more >This paper considers elimination algorithms for sparse matrices over finite fields. We mostly focus on computing the rank, because it raises the same challenges as solving linear systems, while being slightly simpler. We developed a new sparse elimination algorithm inspired by the Gilbert-Peierls sparse LU factorization, which is well-known in the numerical computation community. We benchmarked it against the usual right-looking sparse gaussian elimination and the Wiedemann algorithm using the Sparse Integer Matrix Collection of Jean-Guillaume Dumas. We obtain large speedups (1000× and more) on many cases. In particular , we are able to compute the rank of several large sparse matrices in seconds or minutes, compared to days with previous methods.Show less >

Language :

Anglais

Peer reviewed article :

Oui

Audience :

Internationale

Popular science :

Non

ANR Project :

Chiffrements authentifiés et résistants aux attaques par canaux auxiliaires

Collections :