Combinatorial Optimization of Matrix-Vector Multiplication

Michael Wolf, University of Illinois at Urbana-Champaign

My research focuses primarily on combinatorial problems arising in scientific computing. In particular, I’ve been working on the combinatorial optimization of matrix-vector multiplication, motivated as an important step in the evaluation of finite element stiffness matrices. The general idea is to use linear dependencies and other relationships between rows to generate a more efficient set of operations to perform matrix-vector multiplication. I have formulated and solved a graph problem that uses binary row relationships and determines which operations should be used to compute the matrix-vector product. This graph model is an improvement over previous models since it extends the set of binary row relationships utilized and solves this combinatorial optimization problem optimally for the row relationships implemented.


The aforementioned graph model is limited to binary row relationships since edges have only two vertices. More recently, I have extended the representation by using hypergraphs to model more complicated row relationships, expressing an n-row relationship with an n-vertex hyperedge. My initial greedy algorithm for this hypergraph model has yielded significantly better results than the graph model for many finite element matrices.

Abstract Author(s): Michael Wolf