Seminars & Events

Mathematics and Computer Science Division Seminar
"Optimizing Matrix-Vector Multiplication with Combinatorial Techniques"

DATE: March 16, 2009
TIME: 10:30 AM - 12:00 AM
SPEAKER: Michael Wolf, University of Illinois, Urbana-Champaign
LOCATION: Building 221 Conference Room A216, Argonne National Laboratory
HOST: Boyana Norris

Description:
In this talk, I will describe my work on optimizing matrix-vector multiplication with combinatorial techniques. My research has focused on two different combinatorial scientific computing topics related to matrix-vector multiplication.

For the first topic, I address the optimization of serial matrix-vector multiplication for relatively small, dense matrices, which can be used in finite element assembly. Previous work showed that combinatorial optimization of matrix-vector multiplication can lead to faster evaluation of finite element stiffness matrices by removing redundant operations. Based on a graph model characterizing row relationships, a more efficient set of operations can be generated to perform matrix-vector multiplication. I 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.

For the second topic, I address 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.

Save the event to your calendar [schedule.ics]