Files in this item



application/pdf9010841.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
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
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)

Item Statistics