Using Random Butterfly Transformations to Avoid Pivoting in Sparse Direct Methods

Abstract : We consider the solution of sparse linear systems using direct methods via LU factorization. Unless the matrix is positive definite, numerical pivoting is usually needed to ensure stability, which is costly to implement especially in the sparse case. The Random Butterfly Transformations (RBT) technique provides an alternative to pivoting and is easily parallelizable. The RBT transforms the original matrix into another one that can be factorized without pivoting with probability one. This approach has been successful for dense matrices; in this work, we investigate the sparse case. In particular, we address the issue of fill-in in the transformed system.
Type de document :
Communication dans un congrès
High Performance Computing for Computational Science (VECPAR 2014), Jun 2014, EUGENE (OR), United States. Springer, 8969, 2015, Lecture Notes in Computer Science. 〈http://dx.doi.org/10.1007/978-3-319-17353-5_12〉. 〈10.1007/978-3-319-17353-5_12〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01205703
Contributeur : Marc Baboulin <>
Soumis le : samedi 26 septembre 2015 - 18:22:44
Dernière modification le : jeudi 5 avril 2018 - 12:30:23

Lien texte intégral

Identifiants

Collections

Citation

Marc Baboulin, Xiaoye S. Li, Rouet François-Henry. Using Random Butterfly Transformations to Avoid Pivoting in Sparse Direct Methods. High Performance Computing for Computational Science (VECPAR 2014), Jun 2014, EUGENE (OR), United States. Springer, 8969, 2015, Lecture Notes in Computer Science. 〈http://dx.doi.org/10.1007/978-3-319-17353-5_12〉. 〈10.1007/978-3-319-17353-5_12〉. 〈hal-01205703〉

Partager

Métriques

Consultations de la notice

140