sparsedense

Sparsedense is a hybrid data representation for matrices and tensors that combines sparse and dense storage within a unified structure. It targets data with a mixed density pattern, where some subregions are dense while others are largely empty. The core idea is to partition a matrix into blocks and store each block using the most appropriate format for its density.

Formally, a sparsedense matrix A is partitioned into blocks Aij. For each block, a density measure d(Aij) is computed as the ratio of nonzero entries to the block size. A block is stored as dense if d(Aij) exceeds a chosen threshold, otherwise it is stored in a sparse format such as CSR or CSC. The overall structure maintains metadata about the block partitioning and the storage format of each block, enabling block-wise operations without forcing a uniform format across the entire matrix.

Operations on sparsedense matrices are performed blockwise. For matrix-vector products, dense blocks use standard dense multiplication, while sparse blocks use their native sparse multiplication routines. Block-level operations can be parallelized, and the sparse blocks often contribute to memory savings, while dense blocks leverage efficient CPU cache usage. This approach is well suited to block-structured problems where sparsity is not uniform, such as certain finite element discretizations, graph representations with dense communities, and kernel or covariance matrices with localized dense regions.

Advantages include improved memory efficiency and potential performance gains from matching storage to data access patterns. Challenges involve choosing partitioning strategies, setting density thresholds, and ensuring compatibility with linear algebra libraries.