Task scheduling for parallel sparse Cholesky factorization

Research output: Contribution to journalArticlepeer-review

50 Scopus citations

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 languageEnglish
Pages (from-to)291-314
Number of pages24
JournalInternational Journal of Parallel Programming
Volume18
Issue number4
DOIs
StatePublished - Aug 1989

Keywords

  • Parallel computing
  • sparse Cholesky factorization
  • task scheduling

Fingerprint

Dive into the research topics of 'Task scheduling for parallel sparse Cholesky factorization'. Together they form a unique fingerprint.

Cite this