一句话：提出基于整数多面体并集的 UZP 稀疏格式，统一 CSR/COO 等格式并支持模块化调优 SpMV 性能。
稀疏矩阵计算中，CSR、COO 等通用格式难以充分利用特定稀疏模式，而专用格式常缺乏灵活性与互操作性。本文提出 UZP，一种基于整数点多面体集合的稀疏格式：将稀疏结构表示为若干整数多面体的并集，每个多面体再与仿射格相交，从而统一涵盖 CSR、COO、DIA、BCSR 等格式。UZP 采用模块化构建与优化，通过捕获稀疏结构的等价类，支持面向目标平台和应用需求的表示调优；可由整数坐标构建，并与现有 CSR/COO 软件互操作。作者在 SuiteSparse 的 200 多个矩阵上评估 CPU 上的 SpMV，表明简单且大多未优化的通用执行器已能利用 Z-多面体结构获得稳健性能。
Sparse 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 presents 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 layouts. 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 𝒵-polyhedra structures.
@article{paperbot3130,
title = {Modular Construction and Optimization of the UZP Sparse Format for SpMV on CPUs},
author = {Alonso Rodríguez-Iglesias and Santoshkumar T. Tongli and Emily Tucker and Louis-Noël Pouchet and Gabriel Rodríguez and Juan Touriño},
journal = {Proceedings of the ACM on Programming Languages},
volume = {9},
number = {PLDI},
year = {2025},
doi = {10.1145/3729335}
}