From 2003 to 2009, I was a graduate student at the University of Illinois
at UrbanaChampaign Department of Computer Science under the direction of
Michael Heath.
From 2003 to 2007, I was a
Department of Energy Computational Science Graduate Fellow.
My thesis was entitled "Hypergraph Based Combinatorial Optimization of MatrixVector Multiplication"
and dealt primarily with two Combinatorial Scientific Computing problems.
The unifying theme in the work was that for both problems I used graph and hypergraph
models to improve the performance of important numerical kernels.
TwoDimensional Sparse Matrix Partitioning
2D Partition of
cage5
Matrix

In work collaborating with Erik Boman at Sandia National Laboratories, we researched 2D
partitioning of sparse matrices in order to improve the parallel performance of sparse matrix
kernels such as matrixvector multiplication.
Typically people use 1D methods for partitioning sparse matrices.
However, for certain problems these 1D partitions can result in high communication volumes in the
parallel computation.
In these cases, more general 2D methods are needed in order to obtain good parallel efficiency.
We developed two such 2D partitioning methods for sparse matrices.
One of our methods, the nested dissection partitioning method, has been shown to be one of the best
partitioning methods for sparse matrices from several application areas.
This new method is competitive with the traditional best 2D algorithm (finegrain hypergraph method) in terms of communication volume,
but requires fewer messages and less time to obtain the partition.
The nested dissection method is particularly effective on structurally symmetric matrices,
where it is about as fast to compute as 1D methods and the communication volume is significantly reduced (up to 97%) compared to 1D layout.
The plan is for these new methods (as well as previously developed methods) to be integrated into
Isorropia,
so they will be readily available for
Trilinos users.
Optimization of MatrixVector Multiplication in Finite Element Assembly
Graph Model Example for Optimizing MatrixVector Multiplication

In previous work, Kirby et al. showed that combinatorial optimization of matrixvector multiplication
could lead to faster evaluation of finite element stiffness matrices.
Based on a graph model characterizing relationships between rows, an efficient set of operations
can be generated to perform matrixvector multiplication for this problem.
In our work, we improved the graph model by extending the set of binary row
relationships and solved this combinatorial optimization problem optimally for the binary row relationships implemented, yielding significantly improved results over previous published graph
models.
We also extended the representation by using hypergraphs to model more complicated row relationships,
expressing a threerow relationship with a threevertex hyperedge, for example.
Our initial greedy algorithm for this hypergraph model yielded significantly
better results than the graph model for many matrices.
Papers
Michael M. Wolf,
"HypergraphBased Combinatorial Optimization of MatrixVector Multiplication."
PhD thesis, University of Illinois at UrbanaChampaign, July 2009.
M.M. Wolf, E.G. Boman, and C. Chevalier,
"Improved Parallel Data Partitioning by Nested Dissection with Applications to Information Retrieval."
(In preparation.)
Michael M. Wolf and Michael T. Heath,
"Combinatorial Optimization of MatrixVector Multiplication in Finite Element Assembly,"
SIAM Journal on Scientific Computing, Volume 31, Issue 4, 2009, pp. 29602980.
(preprint)
Erik G. Boman and Michael M. Wolf,
"A Nested Dissection Approach to Sparse Matrix Partitioning."
(submitted paper.)
M. M. Wolf, E.G. Boman, and B. Hendrickson,
"Optimizing Parallel Sparse MatrixVector Multiplication by Corner Partitioning,"
PARA08, Trondheim, Norway, May 2008.
(preprint)
Michael M. Wolf and Erik G. Boman,
"Partitioning for Parallel Sparse MatrixVector Multiplication,"
SANDIA Technical Report SAND20077977, Sandia National Laboratories, 2007, pp. 7586.
J. Ray, B. M. Adams, K. D. Devine, Y. M. Marzouk, M. M. Wolf, and H. N. Najm,
"Distributed MicroReleases of Bioterror Pathogens: Threat Characterizations and Epidemiology
from Uncertain Patient Observables,"
SANDIA Technical Report SAND20086044, Sandia National Laboratories.

Michael M. Wolf — Postdoc
Contact
mmwolf@sandia.gov
(505) 2849963
Mailing Address
Sandia National Labs
CSRI/155
P.O. Box 5800
Albuquerque, NM 871851320
