Parallel Sparse PLUQ Factorization modulo p

Abstract : In this paper, we present the results of our experiments to compute the rank of several large sparse matrices from Dumas's Sparse Integer Matrix Collection, by computing sparse PLUQ factorizations. Our approach consists in identifying as many pivots as possible before performing any arithmetic operation, based solely on the location of non-zero entries in the input matrix. These " structural " pivots are then all eliminated in parallel, in a single pass. We describe several heuristic structural pivot selection algorithms (the problem is NP-hard). These algorithms allows us to compute the ranks of several large sparse matrices in a few minutes, versus many days using Wiedemann's algorithm. Lastly, we describe a multi-thread implementation using OpenMP achieving 70% parallel efficiency on 24 cores on the largest benchmark.
Type de document :
Communication dans un congrès
PASCO'17, Jul 2017, Kaiserslautern, Germany. ACM, pp.1 - 10, 2017, PASCO 2017 - Proceedings of the International Workshop on Parallel Symbolic Computation. 〈http://sigsam.org/PASCO/2017/〉. 〈10.1145/3115936.3115944〉
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01646133
Contributeur : Charles Bouillaguet <>
Soumis le : mardi 5 décembre 2017 - 11:41:05
Dernière modification le : jeudi 7 décembre 2017 - 01:11:47

Fichier

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

Identifiants

Citation

Charles Bouillaguet, Claire Delaplace, Marie-Emilie Voge. Parallel Sparse PLUQ Factorization modulo p. PASCO'17, Jul 2017, Kaiserslautern, Germany. ACM, pp.1 - 10, 2017, PASCO 2017 - Proceedings of the International Workshop on Parallel Symbolic Computation. 〈http://sigsam.org/PASCO/2017/〉. 〈10.1145/3115936.3115944〉. 〈hal-01646133〉

Partager

Métriques

Consultations de la notice

6

Téléchargements de fichiers

4