{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/13069"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/13069","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Hypergraph-Based Combinatorial Optimization of Matrix-Vector Multiplication","abstract":"Combinatorial scientific computing plays an important enabling role in computational science, particularly in high performance scientific computing. In this thesis, we will describe our work on optimizing matrix-vector multiplication using combinatorial techniques. Our research has focused on two different problems in combinatorial scientific computing, both involving matrix-vector multiplication, and both are solved using hypergraph models. For both of these problems, the cost of the combinatorial optimization process can be effectively amortized over many matrix-vector products. The first problem we address is optimization of serial matrix-vector multiplication for relatively small, dense matrices that arise in finite element assembly. Previous work showed that combinatorial optimization of matrix-vector multiplication can lead to faster assembly of finite element stiffness matrices by eliminating redundant operations. Based on a graph model characterizing row relationships, a more efficient set of operations can be generated to perform matrix-vector multiplication. We improved this graph model by extending the set of binary row relationships and using hypergraphs to model more complicated row relationships, yielding significantly improved results over previous models. The second problem we address is parallel matrix-vector multiplication for large sparse matrices. Parallel sparse matrix-vector multiplication is a particularly important numerical kernel in computational science. We have focused on optimizing the parallel performance of this operation by reducing the communication volume through smarter, two-dimensional matrix partitioning. We have developed and implemented a recursive algorithm based on nested dissection to partition structurally symmetric matrices. In general, this method has proven to be the best available for partitioning structurally symmetric matrices (when considering both volume and partitioning time) and has shown great promise for information retrieval matrices. We also developed a second, simpler method that is fast and works well for many symmetric matrices.","abstract_html":"Combinatorial scientific computing plays an important enabling role in computational science, particularly in high performance scientific computing. In this thesis, we will describe our work on optimizing matrix-vector multiplication using combinatorial techniques. Our research has focused on two different problems in combinatorial scientific computing, both involving matrix-vector multiplication, and both are solved using hypergraph models. For both of these problems, the cost of the combinatorial optimization process can be effectively amortized over many matrix-vector products. The first problem we address is optimization of serial matrix-vector multiplication for relatively small, dense matrices that arise in finite element assembly. Previous work showed that combinatorial optimization of matrix-vector multiplication can lead to faster assembly of finite element stiffness matrices by eliminating redundant operations. Based on a graph model characterizing row relationships, a more efficient set of operations can be generated to perform matrix-vector multiplication. We improved this graph model by extending the set of binary row relationships and using hypergraphs to model more complicated row relationships, yielding significantly improved results over previous models. The second problem we address is parallel matrix-vector multiplication for large sparse matrices. Parallel sparse matrix-vector multiplication is a particularly important numerical kernel in computational science. We have focused on optimizing the parallel performance of this operation by reducing the communication volume through smarter, two-dimensional matrix partitioning. We have developed and implemented a recursive algorithm based on nested dissection to partition structurally symmetric matrices. In general, this method has proven to be the best available for partitioning structurally symmetric matrices (when considering both volume and partitioning time) and has shown great promise for information retrieval matrices. We also developed a second, simpler method that is fast and works well for many symmetric matrices.","abstract_has_math":false,"creators":["Wolf, Michael M."],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":["Heath, Michael T.","Boman, Erik G.","Erickson, Jeff G.","Gropp, William D.","Olson, Luke N."],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2009,"date_issued":"2009-07-11T02:37:02Z","date_published":"2009-07-11T02:37:02Z","updated_at":"2026-07-22T22:25:00Z","subjects":["matrix-vector multiplication","hypergraphs","combinatorial optimization","parallel data distributions","finite elements","sparse matrix computations","combinatorial scientific computing"],"languages":["en"],"rights":[],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/13069","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Heath, Michael T.","Boman, Erik G.","Erickson, Jeff G.","Gropp, William D.","Olson, Luke N."]},{"key":"dc:creator","label":"Author","values":["Wolf, Michael M."]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2009-07-11T02:37:02Z","2009-07-11"]},{"key":"dc:type","label":"Dc Type","values":["Dissertation / Thesis","text","other"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"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":["matrix-vector multiplication","hypergraphs","combinatorial optimization","parallel data distributions","finite elements","sparse matrix computations","combinatorial scientific computing"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/13069"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Combinatorial scientific computing plays an important enabling role in computational science, particularly in high performance scientific computing. In this thesis, we will describe our work on optimizing matrix-vector multiplication using combinatorial techniques. Our research has focused on two different problems in combinatorial scientific computing, both involving matrix-vector multiplication, and both are solved using hypergraph models. For both of these problems, the cost of the combinatorial optimization process can be effectively amortized over many matrix-vector products. The first problem we address is optimization of serial matrix-vector multiplication for relatively small, dense matrices that arise in finite element assembly. Previous work showed that combinatorial optimization of matrix-vector multiplication can lead to faster assembly of finite element stiffness matrices by eliminating redundant operations. Based on a graph model characterizing row relationships, a more efficient set of operations can be generated to perform matrix-vector multiplication. We improved this graph model by extending the set of binary row relationships and using hypergraphs to model more complicated row relationships, yielding significantly improved results over previous models. The second problem we address is parallel matrix-vector multiplication for large sparse matrices. Parallel sparse matrix-vector multiplication is a particularly important numerical kernel in computational science. We have focused on optimizing the parallel performance of this operation by reducing the communication volume through smarter, two-dimensional matrix partitioning. We have developed and implemented a recursive algorithm based on nested dissection to partition structurally symmetric matrices. In general, this method has proven to be the best available for partitioning structurally symmetric matrices (when considering both volume and partitioning time) and has shown great promise for information retrieval matrices. We also developed a second, simpler method that is fast and works well for many symmetric matrices.","is peer reviewed","Submitted by Michael Wolf (mmwolf@illinois.edu) on 2009-07-11T02:37:01Z No. of bitstreams: 1 mmwolfThesisFinal.pdf: 1294566 bytes, checksum: c24145e0f72c2bd6d8f0f02885ca4ad0 (MD5)","Made available in DSpace on 2009-07-11T02:37:02Z (GMT). No. of bitstreams: 1 mmwolfThesisFinal.pdf: 1294566 bytes, checksum: c24145e0f72c2bd6d8f0f02885ca4ad0 (MD5) Previous issue date: 2009-07-11","Item marked as restricted to the 'Administrator' Group (id=1) by Sarah Shreeves (sshreeve@illinois.edu) on 2009-07-11T20:49:56Z Item is restricted until 2010-07-11T20:49:56Z","Item reinstated by Sarah Shreeves (sshreeve@illinois.edu) on 2010-07-12T10:00:16Z Item was in collections: Dissertations and Theses - Computer Science (ID: 587) University of Illinois Dissertations and Theses (ID: 204) No. of bitstreams: 2 mmwolfThesisFinal.pdf: 1294566 bytes, checksum: c24145e0f72c2bd6d8f0f02885ca4ad0 (MD5) mmwolfThesisFinal.pdf.txt: 291820 bytes, checksum: ce6d9a7d4a7bbdd5591c8fca52fdb28a (MD5)","Item released from any restrictions by Sarah Shreeves (sshreeve@illinois.edu) on 2010-07-12T10:00:18Z","unpublished"]},{"key":"dc:title","label":"Title","values":["Hypergraph-Based Combinatorial Optimization of Matrix-Vector Multiplication"]}]}],"canonical_facts":{"dc:contributor":["Heath, Michael T.","Boman, Erik G.","Erickson, Jeff G.","Gropp, William D.","Olson, Luke N."],"dc:creator":["Wolf, Michael M."],"dc:date":["2009-07-11T02:37:02Z","2009-07-11"],"dc:description":["Combinatorial scientific computing plays an important enabling role in computational science, particularly in high performance scientific computing. In this thesis, we will describe our work on optimizing matrix-vector multiplication using combinatorial techniques. Our research has focused on two different problems in combinatorial scientific computing, both involving matrix-vector multiplication, and both are solved using hypergraph models. For both of these problems, the cost of the combinatorial optimization process can be effectively amortized over many matrix-vector products. The first problem we address is optimization of serial matrix-vector multiplication for relatively small, dense matrices that arise in finite element assembly. Previous work showed that combinatorial optimization of matrix-vector multiplication can lead to faster assembly of finite element stiffness matrices by eliminating redundant operations. Based on a graph model characterizing row relationships, a more efficient set of operations can be generated to perform matrix-vector multiplication. We improved this graph model by extending the set of binary row relationships and using hypergraphs to model more complicated row relationships, yielding significantly improved results over previous models. The second problem we address is parallel matrix-vector multiplication for large sparse matrices. Parallel sparse matrix-vector multiplication is a particularly important numerical kernel in computational science. We have focused on optimizing the parallel performance of this operation by reducing the communication volume through smarter, two-dimensional matrix partitioning. We have developed and implemented a recursive algorithm based on nested dissection to partition structurally symmetric matrices. In general, this method has proven to be the best available for partitioning structurally symmetric matrices (when considering both volume and partitioning time) and has shown great promise for information retrieval matrices. We also developed a second, simpler method that is fast and works well for many symmetric matrices.","is peer reviewed","Submitted by Michael Wolf (mmwolf@illinois.edu) on 2009-07-11T02:37:01Z No. of bitstreams: 1 mmwolfThesisFinal.pdf: 1294566 bytes, checksum: c24145e0f72c2bd6d8f0f02885ca4ad0 (MD5)","Made available in DSpace on 2009-07-11T02:37:02Z (GMT). No. of bitstreams: 1 mmwolfThesisFinal.pdf: 1294566 bytes, checksum: c24145e0f72c2bd6d8f0f02885ca4ad0 (MD5) Previous issue date: 2009-07-11","Item marked as restricted to the 'Administrator' Group (id=1) by Sarah Shreeves (sshreeve@illinois.edu) on 2009-07-11T20:49:56Z Item is restricted until 2010-07-11T20:49:56Z","Item reinstated by Sarah Shreeves (sshreeve@illinois.edu) on 2010-07-12T10:00:16Z Item was in collections: Dissertations and Theses - Computer Science (ID: 587) University of Illinois Dissertations and Theses (ID: 204) No. of bitstreams: 2 mmwolfThesisFinal.pdf: 1294566 bytes, checksum: c24145e0f72c2bd6d8f0f02885ca4ad0 (MD5) mmwolfThesisFinal.pdf.txt: 291820 bytes, checksum: ce6d9a7d4a7bbdd5591c8fca52fdb28a (MD5)","Item released from any restrictions by Sarah Shreeves (sshreeve@illinois.edu) on 2010-07-12T10:00:18Z","unpublished"],"dc:identifier":["http://hdl.handle.net/2142/13069"],"dc:language":["en"],"dc:subject":["matrix-vector multiplication","hypergraphs","combinatorial optimization","parallel data distributions","finite elements","sparse matrix computations","combinatorial scientific computing"],"dc:title":["Hypergraph-Based Combinatorial Optimization of Matrix-Vector Multiplication"],"dc:type":["Dissertation / Thesis","text","other"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:25:00Z"}