Applicability of Pattern-based sparse matrix representation for real applications

Pattern-based representation (PBR) is a novel sparse matrix representation that reduces the index overhead for many matrices without zero-filling and without requiring the identification of dense matrix blocks. The PBR analyzer identifies recurring block nonzero patterns, represents the submatrix consisting of all blocks of this pattern in block coordinate format, and generates custom matrix-vector multiplication kernels for that submatrix. In this way, PBR expresses matrix structure in terms of specialized inner loops, thereby creating locality for repeating structure via the instruction cache, and reducing the amount of index data that must be fetched from memory. In this paper we evaluate the applicability of PBR by testing it on a large set of matrices from the University of Florida sparse matrix collection. We analyze PBR’s suitability for a wide range of problems and identify underlying problem and matrix characteristics that suggest good performance with PBR. We find that PBR is especially promising for problems with underlying 2D/3D geometry.