inria-00069935, version 1
Using Postordering and Static Symbolic Factorization for Parallel Sparse LU
N° RT-0237 (1999)
Résumé : In this report we present several improvements of widely used parallel LU factorization methods on sparse matrices. First we characterize the L, U factors in terms of their corresponding LU elimination forest. This characterization can be used as a compact storage scheme of the matrix as well as of the task dependence graph. To improve the use of BLAS in the numerical factorization, we perform a postorder traversal of the LU eforest thus obtaining larger supernodes. To expose more task parallelism for a sparse matrix, we build a more accurate task dependence graph that includes only the least necessary dependencies. Experiments compared favorably our methods against methods implemented in the S* environment on the SGI's Origin2000 multiprocessor.
- 1 :
- INRIA – Université Henri Poincaré - Nancy I – Université Nancy II – Institut National Polytechnique de Lorraine (INPL) – CNRS : UMR7503
- Domaine : Informatique/Autre
- Mots-clés : sparse unsymmetric matrices – gaussian elimination – partial pivoting – static symbolic factorization – elimination tree – postordering – SHMEM
- Référence interne : RT-0237
- inria-00069935, version 1
- http://hal.inria.fr/inria-00069935
- oai:hal.inria.fr:inria-00069935
- Contributeur :
- Soumis le : Vendredi 19 Mai 2006, 18:37:20
- Dernière modification le : Mercredi 21 Juin 2006, 16:04:46





Documents associés

Exporter