Abstract
This paper presents a solution to the problem of partitioning the work for sparse matrix factorization to individual processors on a multiprocessor system. The proposed task assignment strategy is based on the structure of the elimination tree associated with the given sparse matrix. The goal of the task scheduling strategy is to achieve load balancing and a high degree of concurrency among the processors while reduçing the amount of processor-to-processor data comnication, even for arbitrarily unbalanced elimination trees. This is important because popular fill-reducing ordering methods, such as the minimum degree algorithm, often produce unbalanced elimination trees. Results from the Intel iPSC/2 are presented for various finite-element problems using both nested dissection and minimum degree orderings.
Original language | English |
---|---|
Pages (from-to) | 291-314 |
Number of pages | 24 |
Journal | International Journal of Parallel Programming |
Volume | 18 |
Issue number | 4 |
DOIs | |
State | Published - Aug 1989 |
Keywords
- Parallel computing
- sparse Cholesky factorization
- task scheduling