IDEALS Home University of Illinois at Urbana-Champaign logo The Alma Mater The Main Quad

A parallel algorithm for sparse unsymmetric LU factorization

Show full item record

Bookmark or cite this item:

Files in this item

File Description Format
PDF 9010841.pdf (8MB) Restricted to U of Illinois (no description provided) PDF
Title: A parallel algorithm for sparse unsymmetric LU factorization
Author(s): Davis, Timothy Alden
Doctoral Committee Chair(s): Yew, Pen-Chung
Department / Program: Electrical and Computer Engineering
Discipline: Electrical Engineering
Degree Granting Institution: University of Illinois at Urbana-Champaign
Degree: Ph.D.
Genre: Dissertation
Subject(s): Mathematics Engineering, Electronics and Electrical Computer Science
Abstract: This thesis presents a parallel algorithm for the direct LU factorization of general unsymmetric sparse matrices. The algorithm, D2, is based on a new nondeterministic parallel pivot search that finds a compatible pivot set S of size m, followed by a parallel rank-m update. These two steps alternate until switching to dense matrix code or until the matrix is factored. The algorithm is based on a shared-memory MIMD model and takes advantage of both concurrency and (gather-scatter) vectorization. Experimental comparisons on an Alliant FX/8 show that the method results in shorter elimination trees for matrices with highly asymmetrical nonzero structure than those for previous methods that work with the symmetric structure of A + ${\bf A\sp{T}}$ or ${\bf A\sp{T}A}$ (such as George and Ng's Sparspak-C or Duff and Reid's multifrontal method). The algorithm exploits more parallelism in the pivot search phase than previous algorithms which do not force a symmetric structure onto the matrix during any phase of the factorization. Additional experimental comparisons include fillin, amount of work, numerical stability, memory usage, and run time. The nondeterministic behavior of the D2 algorithm and other performance metrics are analyzed on an Alliant FX/8, a Cray-2, and a Cray-XMP/48. Enhancements to PSolve, a pairwise pivoting algorithm, are discussed, and a software tool for developing sparse matrix algorithms and observing their dynamic behavior on a Sun workstation is presented. The tool was instrumental in the development of the D2 algorithm. Possible extensions to the D2 algorithm are discussed, including the use of dense matrix kernels and replacing the synchronization structure in the pivot search with a software combining tree.
Issue Date: 1989
Type: Text
Language: English
Rights Information: Copyright 1989 Davis, Timothy Alden
Date Available in IDEALS: 2011-05-07
Identifier in Online Catalog: AAI9010841
OCLC Identifier: (UMI)AAI9010841

This item appears in the following Collection(s)

Show full item record

Item Statistics

  • Total Downloads: 1
  • Downloads this Month: 0
  • Downloads Today: 0


My Account


Access Key