Computational models and task scheduling for parallel sparse Cholesky factorization

DOI10.1016/0167-8191(86)90014-1MaRDI QIDQ1086977zbMATH OpenOpenAlexFDO

Authors Joseph W. H. Liu

Publication date 1986

Published in Parallel Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0167-8191(86)90014-1

zbMATH Keywords

fill-reducing orderingmedium- grained graph modelminimum degree orderingnumeric factorizationparallel sparse Cholesky factorizationscheduling

Mathematics Subject Classification ID

Direct numerical methods for linear systems and matrix inversion (65F05) Computational methods for sparse matrices (65F50)

Review text

The numerical solution of linear systems has the following typical phases: ordering, symbolic factorization, numeric factorization, and numeric substitution. In this paper the numeric factorization phase for parallel computation is studied. A parallel sparse Cholesky factorization algorithm is formulated. It is suitable for parallel machines with shared-memory architecture, like Denelcor HEP. The algorithm is based on the medium-grained graph model of column-oriented tasks and a critical path type of scheduling. A variant of the scheme allowing preemption is also described. The algorithm assumes that the given matrix has already been ordered by some fill-reducing ordering algorithm, e.g. the minimum degree ordering.

Recommendations

• Task scheduling for parallel sparse Cholesky factorization
• Parallel sparse Cholesky factorization on a shared memory multiprocessor
• Parallel Algorithms for Sparse Linear Systems
• scientific article; zbMATH DE number 833696
• scientific article; zbMATH DE number 1760069

Cited in

(17)

• Assignment and scheduling in parallel matrix factorization
• The formal development of a parallel program performing LU-decomposition
• Solution of sparse positive definite systems on a shared-memory multiprocessor
• A parallel graph partitioning algorithm for a message-passing multiprocessor
• Solution of sparse positive definite systems on a hypercube
• Efficient decomposition and performance of parallel PDE, FFT, Monte Carlo simulations, simplex, and sparse solvers
• Decomposition in multidimensional Boolean-optimization problems with sparse matrices
• Multiprocessing a sparse matrix code on the Alliant FX/8
• scientific article; zbMATH DE number 18296 (Why is no real title available?)
• Parallel Algorithms for Sparse Linear Systems
• scientific article; zbMATH DE number 1760069 (Why is no real title available?)
• On evaluating elimination tree based parallel sparse cholesky factorizations
• A survey of direct methods for sparse linear systems
• Parallel selected inversion for space-time Gaussian Markov random fields
• Hitting sets online and unique-MAX coloring
• Parallel sparse Gaussian elimination with partial pivoting
• Task scheduling for parallel sparse Cholesky factorization

This page was built for publication: Computational models and task scheduling for parallel sparse Cholesky factorization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1086977)