Pfeil, FlorianFerreira, StephanieMueller-Roemer, Johannes SebastianEgger, BernhardGünther, Tobias2025-09-242025-09-242025978-3-03868-294-3https://doi.org/10.2312/vmv.20251245https://diglib.eg.org/handle/10.2312/vmv20251245We present Binned Variable Block Compressed Sparse Row (Bin-VBSR), a novel GPU-optimized sparse matrix data structure and associated sparse matrix-vector multiplication algorithm for matrices with variable-size dense blocks. This includes a novel approach to handling long rows in the Binned Compressed Sparse Row (Bin-CSR) family of GPU-optimized sparse matrix data structures. We demonstrate speedups of up to 9.9× over Bin-BCSR* and extend its data compression advantages over compressed sparse row (CSR) to variable block size, resulting in an improvement of up to 50%.Attribution 4.0 International LicenseCCS Concepts: Computing methodologies → Massively parallel algorithms; Mathematics of computing → Computations on matrices; Mathematical software performanceComputing methodologies → Massively parallel algorithmsMathematics of computing → Computations on matricesMathematical software performance10.2312/vmv.202512458 pages