8494 articles  [english version]

inria-00069935, version 1

Using Postordering and Static Symbolic Factorization for Parallel Sparse LU

Michel Cosnard () 1, Laura Grigori 1

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 :  RESEDAS (INRIA Lorraine - LORIA)
  • 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
  • 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