Argonne National Laboratory

Upcoming Events

Matrix Multiplications: A Lot of Ways of Handling a Few Nonzeros

Series 
LANS Informal Seminar
Presenter 
Karl Rupp (MCS)
September 27, 2017 3:00PM to 4:00PM
Location 
Building 240, Room 4301
Type 
Seminar

Abstract: Optimizing the implementation of dense matrix-matrix multiplication kernels often boils down to finding a single, outstanding implementation for a particular machine. If the matrices involved have only few nonzeros, however, there is no longer a single, outstanding implementation. Instead, the fastest algorithm and the fastest implementation depend on details such as the particular location as well as the number of nonzeros of the matrices involved. As a consequence, libraries such as PETSc include implementations of different algorithms for matrix-matrix multiplications of such sparsely populated matrices.

This talk explains the concepts underlying the different algorithms for sparse matrix-matrix multiplications. The audience will learn how these concepts carry over to graph algorithms and how the use of hardware features such as vector registers may result in better performance. By considering a range of typical applications with characteristic nonzero patterns, an inexpensive heuristic is proposed to select a fast sparse matrix-matrix multiplication implementation for the matrices provided.