{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/20745"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/20745","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"A parallel algorithm for sparse unsymmetric LU factorization","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.","abstract_html":"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.","abstract_has_math":true,"creators":["Davis, Timothy Alden"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Electrical Engineering","degree_department":null,"school":null,"contributors":["Yew, Pen-Chung"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2011,"date_issued":"2011-05-07T12:48:01Z","date_published":"2011-05-07T12:48:01Z","updated_at":"2026-07-22T22:25:16Z","subjects":["Mathematics","Engineering, Electronics and Electrical","Computer Science"],"languages":["eng"],"rights":["Copyright 1989 Davis, Timothy Alden"],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["AAI9010841","(UMI)AAI9010841"],"render_values":[{"text":"AAI9010841","href":null,"code":true},{"text":"(UMI)AAI9010841","href":null,"code":true}]}]},"links":{"outbound_url":"http://hdl.handle.net/2142/20745","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Yew, Pen-Chung"]},{"key":"dc:creator","label":"Author","values":["Davis, Timothy Alden"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2011-05-07T12:48:01Z","10000-01-01","1989"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Electrical Engineering"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Mathematics","Engineering, Electronics and Electrical","Computer Science"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["eng"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 1989 Davis, Timothy Alden"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["AAI9010841","(UMI)AAI9010841","http://hdl.handle.net/2142/20745"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["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.","Made available in DSpace on 2011-05-07T12:48:01Z (GMT). No. of bitstreams: 2 license.txt: 4922 bytes, checksum: 910b249b4beec47e7ab768910c8f966f (MD5) 9010841.pdf: 8383900 bytes, checksum: 8fef2ba56332e5dc4b4e1d85bf4d98f4 (MD5) Previous issue date: 1989","Item marked as restricted to the 'UIUC Users [automated]' Group (id=2) by Howard Ding (hding2@illinois.edu) on 2011-05-07T14:45:58Z Item is restricted indefinitely.","Restriction data tranferred 2014-07-01T11:20:27-05:00 Original Data Group with Access UIUC Users [automated] Release Date: none Reason: ETDs are only available to UIUC Users without author permission","ETDs are only available to UIUC Users without author permission","U of I Only"]},{"key":"dc:title","label":"Title","values":["A parallel algorithm for sparse unsymmetric LU factorization"]}]}],"canonical_facts":{"dc:contributor":["Yew, Pen-Chung"],"dc:creator":["Davis, Timothy Alden"],"dc:date":["2011-05-07T12:48:01Z","10000-01-01","1989"],"dc:description":["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.","Made available in DSpace on 2011-05-07T12:48:01Z (GMT). No. of bitstreams: 2 license.txt: 4922 bytes, checksum: 910b249b4beec47e7ab768910c8f966f (MD5) 9010841.pdf: 8383900 bytes, checksum: 8fef2ba56332e5dc4b4e1d85bf4d98f4 (MD5) Previous issue date: 1989","Item marked as restricted to the 'UIUC Users [automated]' Group (id=2) by Howard Ding (hding2@illinois.edu) on 2011-05-07T14:45:58Z Item is restricted indefinitely.","Restriction data tranferred 2014-07-01T11:20:27-05:00 Original Data Group with Access UIUC Users [automated] Release Date: none Reason: ETDs are only available to UIUC Users without author permission","ETDs are only available to UIUC Users without author permission","U of I Only"],"dc:identifier":["AAI9010841","(UMI)AAI9010841","http://hdl.handle.net/2142/20745"],"dc:language":["eng"],"dc:rights":["Copyright 1989 Davis, Timothy Alden"],"dc:subject":["Mathematics","Engineering, Electronics and Electrical","Computer Science"],"dc:title":["A parallel algorithm for sparse unsymmetric LU factorization"],"dc:type":["text"],"thesis:degree_discipline":["Electrical Engineering"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:25:16Z"}