Files in this item
Files  Description  Format 

application/pdf mmwolfThesisFinal.pdf (1Mb)  Ph.D. Thesis 
Description
Title:  HypergraphBased Combinatorial Optimization of MatrixVector Multiplication 
Author(s):  Wolf, Michael M. 
Doctoral Committee Chair(s):  Heath, Michael T. 
Doctoral Committee Member(s):  Boman, Erik G.; Erickson, Jeff G.; Gropp, William D.; Olson, Luke N. 
Department / Program:  Computer Science 
Discipline:  Computer Science 
Degree Granting Institution:  University of Illinois at UrbanaChampaign 
Degree:  Ph.D. 
Genre:  Dissertation 
Subject(s):  matrixvector multiplication
hypergraphs combinatorial optimization parallel data distributions finite elements sparse matrix computations combinatorial scientific computing 
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 matrixvector multiplication using combinatorial techniques. Our research has focused on two different problems in combinatorial scientific computing, both involving matrixvector 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 matrixvector products. The first problem we address is optimization of serial matrixvector multiplication for relatively small, dense matrices that arise in finite element assembly. Previous work showed that combinatorial optimization of matrixvector 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 matrixvector 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 matrixvector multiplication for large sparse matrices. Parallel sparse matrixvector 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, twodimensional 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. 
Issue Date:  20090711 
Genre:  Dissertation / Thesis 
Type:  Text Other 
Language:  English 
URI:  http://hdl.handle.net/2142/13069 
Publication Status:  unpublished 
Peer Reviewed:  is peer reviewed 
Date Available in IDEALS:  20090711 
This item appears in the following Collection(s)

Dissertations and Theses  Computer Science
Dissertations and Theses from the Dept. of Computer Science 
Graduate Dissertations and Theses at Illinois
Graduate Theses and Dissertations at Illinois
Item Statistics
 Total Downloads: 287
 Downloads this Month: 8
 Downloads Today: 0