HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Conference papers

Using Postordering and Static Symbolic Factorization for Parallel Sparse LU

Michel Cosnard 1 Laura Grigori 1
1 RESEDAS - Software Tools for Telecommunications and Distributed Systems
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : In this paper we present several improvements of widely used parallel LU factorization methods on sparse matrices. First we introduce the LU elimination forest and then 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 elimination forest, 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 dependences.
Document type :
Conference papers
Complete list of metadata

Contributor : Publications Loria Connect in order to contact the contributor
Submitted on : Tuesday, September 26, 2006 - 8:52:01 AM
Last modification on : Friday, February 4, 2022 - 3:22:19 AM


  • HAL Id : inria-00099235, version 1



Michel Cosnard, Laura Grigori. Using Postordering and Static Symbolic Factorization for Parallel Sparse LU. IEEE International Parallel & Distributed Processing Symposium, May 2000, none, pp.807-812. ⟨inria-00099235⟩



Record views