An efficient distributed randomized algorithm for solving large dense symmetric indefinite 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. We propose a randomized solver 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. The contribution of this paper is to propose efficient kernels for applying random butterfly transformations and a new distributed implementation combined with a runtime (PaRSEC) that automatically adjusts data structures, data mappings, and the scheduling as systems scale up. Both the parallel distributed solver and the supporting runtime environment are innovative. To our knowledge, the randomization approach associated with this solver has never been used in public domain software for symmetric indefinite 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 :
Article dans une revue
Liste complète des métadonnées

https://hal.inria.fr/hal-01024857
Contributeur : Marc Baboulin <>
Soumis le : mercredi 16 juillet 2014 - 17:36:38
Dernière modification le : jeudi 11 janvier 2018 - 06:25:42

Identifiants

Citation

Marc Baboulin, Dulceneia Becker, George Bosilca, Anthony Danalis, Jack Dongarra. An efficient distributed randomized algorithm for solving large dense symmetric indefinite linear systems. Parallel Computing, Elsevier, 2014, 40 (7), pp.213-223. 〈http://www.sciencedirect.com/science/article/pii/S0167819113001488〉. 〈10.1016/j.parco.2013.12.003〉. 〈hal-01024857〉

Partager

Métriques

Consultations de la notice

155