Files in this item

FilesDescriptionFormat

application/pdf

9010841.pdf (8MB)
(no description provided)PDF

Description

 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 URI: http://hdl.handle.net/2142/20745 Rights Information: Copyright 1989 Davis, Timothy Alden Date Available in IDEALS: 2011-05-07 Identifier in Online Catalog: AAI9010841 OCLC Identifier: (UMI)AAI9010841
﻿