Parallel Sparse PLUQ Factorization modulo p - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2017

Parallel Sparse PLUQ Factorization modulo p

Résumé

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

Dates et versions

hal-01646133 , version 1 (05-12-2017)

Identifiants

Citer

Charles Bouillaguet, Claire Delaplace, Marie-Emilie Voge. Parallel Sparse PLUQ Factorization modulo p. PASCO'17, Jul 2017, Kaiserslautern, Germany. pp.1 - 10, ⟨10.1145/3115936.3115944⟩. ⟨hal-01646133⟩
192 Consultations
514 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More