An efficient distributed randomized solver with application to large dense linear systems

Abstract : Randomized algorithms are gaining ground in high-performance computing applications as they have the potential to outperform deterministic methods, while still providing accurate results. In this paper, we propose a randomized algorithm for distributed multicore architectures to efficiently solve large dense symmetric indefinite linear systems that are encountered, for instance, in parameter estimation problems or electromagnetism simulations. This solver combines an efficient implementation of a multiplicative preconditioning based on recursive random matrices, with a runtime (DAGuE) that automatically adjusts data structures, data mappings, and the scheduling as systems scale up. Both the solver and the supporting runtime environment are innovative. To our knowledge, this is the first parallel distributed solver for large dense symmetric indefinite systems, and the randomization approach associated with this solver has never been used in public domain software for such systems. The underlying runtime framework allows seamless data mapping and task scheduling, mapping its capabilities to the underlying hardware features of heterogeneous distributed architectures. The performance of our software is similar to that obtained for symmetric positive definite systems, but requires only half the execution time and half the amount of data storage of a general dense solver.
Type de document :
[Research Report] RR-8043, INRIA. 2012
Liste complète des métadonnées

Littérature citée [20 références]  Voir  Masquer  Télécharger
Contributeur : Marc Baboulin <>
Soumis le : mercredi 22 août 2012 - 06:01:31
Dernière modification le : mardi 24 avril 2018 - 13:51:39
Document(s) archivé(s) le : vendredi 16 décembre 2016 - 06:45:59


Fichiers éditeurs autorisés sur une archive ouverte


  • HAL Id : hal-00724059, version 1



Marc Baboulin, Dulceneia Becker, George Bosilca, Anthony Danalis, Jack Dongarra. An efficient distributed randomized solver with application to large dense linear systems. [Research Report] RR-8043, INRIA. 2012. 〈hal-00724059〉



Consultations de la notice


Téléchargements de fichiers