Optimizing sparse computations using union of Z-polyhedra

Abstract

Sparse matrices play a central role in a wide range of modern computational problems. They are especially common in domains such as scientific simulations, numerical methods, graph analytics, machine learning, and high-performance computing workloads, where data is often structured in a way that leads to a significant number of zero-valued elements. Instead of treating these zeros as meaningful data, sparse matrix techniques aim to exploit this sparsity to reduce both storage and computational cost, thereby improving scalability and efficiency. The Union of Z-Polyhedra (UZP) sparse format models sparse structures as unions of integer polyhedra intersected with affine lattices, capturing both regular and irregular sparsity patterns in a unified form. Building on this abstraction, ur work introduces a suite of tuners that apply structural transformations to UZP representations without altering their mathematical semantics. These transformations improve data locality, Single Instruction Multiple Data (SIMD) vectorization, and parallelism, enabling performance tuning without modifying execution logic. Evaluated across 229 matrices from the SuiteSparse collection, the optimized UZP representations achieve highly competitive performance for sparse matrix-vector multiplication (SpMV) computations on multi-core CPUs, outperforming reference approaches such as Intel MKL's sparse implementation or formats dedicated to SIMD vectorization.