Rodríguez-Iglesias, Alonso, authorTongli, Santoshkumar T., authorTucker, Emily, authorPouchet, Louis-Noël, authorRodríguez, Gabriel, authorTouriño, Juan, authorACM, publisher2025-12-222025-12-222025-06-10Alonso Rodríguez-Iglesias, Santoshkumar T. Tongli, Emily Tucker, Louis-Noël Pouchet, Gabriel Rodríguez, and Juan Touriño. 2025. Modular Construction and Optimization of the UZP Sparse Format for SpMV on CPUs. Proc. ACM Program. Lang. 9, PLDI, Article 232 (June 2025), 25 pages. https://doi.org/10.1145/3729335https://hdl.handle.net/10217/242548Sparse data structures are ubiquitous in modern computing, and numerous formats have been designed to represent them. These formats may exploit specific sparsity patterns, aiming to achieve higher performance for key numerical computations than more general-purpose formats such as CSR and COO. In this work we present UZP, a new sparse format based on polyhedral sets of integer points. UZP is a flexible format that subsumes CSR, COO, DIA, BCSR, etc., by raising them to a common mathematical abstraction: a union of integer polyhedra, each intersected with an affine lattice. We present a modular approach to building and optimizing UZP: it captures equivalence classes for the sparse structure, enabling the tuning of the representation for target-specific and application-specific performance considerations. UZP is built from any input sparse structure using integer coordinates, and is interoperable with existing software using CSR and COO data layout. We provide detailed performance evaluation of UZP on 200+ matrices from SuiteSparse, demonstrating how simple and mostly unoptimized generic executors for UZP can already achieve solid performance by exploiting Z-polyhedra structures.born digitalarticlesenghttps://creativecommons.org/licenses/by/4.0sparse linear algebracode generationsparse formatpolyhedral compilationSIMD vectorizationTextThis work is licensed under a Creative Commons Attribution 4.0 International License.https://doi.org/10.1145/3729335