Elsevier

Parallel Computing

Volume 10, Issue 2, April 1989, Pages 177-191
Parallel Computing

Independent set orderings for parallel matrix factorization by Gaussian elimination

https://doi.org/10.1016/0167-8191(89)90016-1Get rights and content

Abstract

Commonly used matrix ordering techniques are designed to minimize fill, i.e., they are designed to minimize the number of zero elements which become nonzero during matrix factorization by Gaussian elimination. If Gaussian elimination is to be implemented on a parallel machine, however, minimum fill orderings are not necessarily optimal. Rather, the primary concern is to order a matrix so as to minimize the time required to complete its factorization. An ordering heuristic which appears to perform well with respect to parallel factorization time is one based on finding independent sets of vertices in the matrix adjacency graph.

References (39)

  • J Edmonds et al.

    Thepretical improvements in algorithmic efficiency for network flow problems

    J. ACM

    (1972)
  • K Efe

    Heuristic models of task assignment scheduling in distributed systems

    Computer

    (1982)
  • G.A Geist et al.

    LU factorization algorithms on distributed memory multiprocessor architectures

  • A George

    Computer implementation of the finite element method

  • A George

    Nested dissection of a regular finite element mesh

    SIAM J. Numer. Anal.

    (1973)
  • A George et al.

    An automatic nested dissection algorithm for irregular finite element problems

    SIAM J. Numer. Anal.

    (1978)
  • A George et al.

    Computer Solution of Large Sparse Positive Definite Systems

    (1981)
  • A George et al.

    Sparse Cholesky factorization on a local-memory multiprocessor

  • A George et al.

    Solution of sparse positive definite systems on a shared-memory multiprocessor

    • Cited by (0)

    View full text
    Copyright © 1989 Published by Elsevier B.V.