Sparse Gaussian Elimination modulo p: an Update
Type de document :
Communication dans un congrès avec actes
Titre :
Sparse Gaussian Elimination modulo p: an Update
Auteur(s) :
Bouillaguet, Charles [Auteur]
Université de Lille
Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 [CRIStAL]
Delaplace, Claire [Auteur]
Université de Rennes [UR]
Institut de Recherche en Informatique et Systèmes Aléatoires [IRISA]
Université de Lille
Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 [CRIStAL]
Delaplace, Claire [Auteur]
Université de Rennes [UR]
Institut de Recherche en Informatique et Systèmes Aléatoires [IRISA]
Titre de la manifestation scientifique :
Computer Algebra in Scientific Computing
Ville :
Bucharest
Pays :
Roumanie
Date de début de la manifestation scientifique :
2016-09-19
Titre de l’ouvrage :
CASC'16
Date de publication :
2016-06-19
Discipline(s) HAL :
Informatique [cs]/Logiciel mathématique [cs.MS]
Résumé en anglais : [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 ...
Lire la suite >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.Lire moins >
Lire la suite >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.Lire moins >
Langue :
Anglais
Comité de lecture :
Oui
Audience :
Internationale
Vulgarisation :
Non
Collections :
Source :
Fichiers
- https://hal.archives-ouvertes.fr/hal-01333670/document
- Accès libre
- Accéder au document
- https://hal.archives-ouvertes.fr/hal-01333670/document
- Accès libre
- Accéder au document
- https://hal.archives-ouvertes.fr/hal-01333670/document
- Accès libre
- Accéder au document
- document
- Accès libre
- Accéder au document
- main.pdf
- Accès libre
- Accéder au document