COO Format (Coordinate Format)

The COO format stores a sparse tensor using three parallel arrays (or lists of tuples) of equal length:

• Coordinates Array(s): One array per dimension (e.g., rows, cols) containing the integer indices of each non-zero element.
• Values Array: A contiguous array containing the data value (e.g., float32) of each corresponding non-zero element. For a 2D matrix with nnz non-zeros, storage requires O(3 * nnz) memory: nnz row indices, nnz column indices, and nnz values. This explicit indexing makes construction and random element access straightforward.

COO's primary advantage is its conceptual and implementation simplicity. It imposes no structural constraints, making it ideal for:

• Dynamic Construction: Easily incrementally assemble a sparse tensor by appending (index, value) tuples.
• Irregular Sparsity: Efficiently represents completely unstructured sparsity patterns where non-zeros are randomly distributed.
• High-Dimensional Tensors: Naturally extends to N-dimensional data by simply adding more coordinate arrays. This flexibility makes COO a common intermediate format in sparse linear algebra libraries, used for constructing matrices before conversion to more operation-optimized formats like CSR or CSC.

The explicit storage of all coordinates leads to significant memory overhead compared to compressed formats. For a matrix, COO uses 2 * nnz integers for indices, while CSR uses nnz + (num_rows + 1) integers. Performance bottlenecks arise from:

• Random Access for Operations: Matrix-vector multiplication (SpMV) requires indirect, non-sequential gathers from the dense vector, causing poor cache utilization.
• Duplicate Entries: The format allows multiple entries for the same coordinate, requiring a summation pass to coalesce duplicates, which adds preprocessing cost.
• No Fast Row Traversal: Unlike CSR, iterating over all non-zeros in a specific row requires scanning the entire rows array, an O(nnz) operation.

COO is best suited for scenarios where its construction benefits outweigh its operational inefficiencies:

• Sparse Tensor I/O & Serialization: A simple, portable format for saving/loading sparse data (e.g., in MLX, SciPy's .npz files).
• Graph Construction: Representing adjacency matrices for graph algorithms where edges are added incrementally.
• Sparse Matrix Assembly in finite element analysis, where element stiffness matrices are summed into a global matrix.
• Conversion Hub: Often used as a canonical format to convert between other sparse formats (e.g., CSR ↔ CSC) due to its symmetric treatment of dimensions.

COO and Compressed Sparse Row (CSR) are the two most common sparse matrix formats. Their key differences are:

• Index Storage: COO stores explicit (row, col) per element. CSR compresses row pointers, storing only col indices per element and a row_ptr array of size num_rows + 1.
• Row-Based Operations: CSR provides O(1) access to the start of a row's data, making SpMV and row-slicing highly efficient. COO does not.
• Construction: Building CSR directly is complex; it's often built via COO.
• Memory: For typical matrices, CSR uses less memory than COO. COO becomes competitive only when nnz is very small or num_rows is very large.

Several optimized variants of COO address its shortcomings:

• Sorted COO: The coordinate arrays are sorted lexicographically (e.g., by row, then column). This enables faster conversion to CSR/CSC and improves cache locality for some operations.
• Blocked COO (BCOO): Groups non-zero values into small, dense blocks (e.g., 2x2). Stores block coordinates and a dense block values array. This reduces index storage overhead and improves arithmetic intensity for structured sparsity.
• Compressed COO: Uses run-length encoding on one dimension (like CSR) but keeps full indices for the other, offering a middle-ground between COO and CSR. These variants illustrate the trade-off space between flexibility, memory footprint, and operational speed inherent to sparse storage.

A compressed sparse matrix format that stores three arrays:

• Row Pointers (RP): An array of length rows + 1 where RP[i] indicates the start index of row i in the column and value arrays.
• Column Indices (CI): An array storing the column index for each non-zero element.
• Values (VAL): An array storing the non-zero values.

Key Difference from COO: CSR compresses the row index information, eliminating the explicit row array. This makes row-wise access and operations like SpMM (Sparse Matrix-Dense Matrix Multiplication) highly efficient, as iterating through all non-zeros in a row is a contiguous memory operation. However, modifying the sparsity structure (adding/removing non-zeros) is more expensive than in COO.

The fundamental computational kernel for multiplying a sparse matrix by a dense matrix. It is the core operation in sparse linear layers of neural networks. Efficient SpMM requires:

• Zero-Skipping: Skipping multiplications where the sparse matrix value is zero.
• Efficient Gather-Scatter: The dense matrix rows must be gathered according to the sparse matrix's column indices, multiplied, and the results scattered (accumulated) into the output matrix according to the row indices.

Performance Factors: The efficiency of SpMM is heavily dependent on the sparse data layout (COO, CSR, etc.), the distribution of non-zeros, and the underlying hardware's ability to handle irregular memory access patterns and load imbalance.

Parallel computing primitives critical for sparse computation on accelerators like GPUs.

• Gather: Reads data from a set of non-contiguous memory addresses (specified by an index array) into a contiguous vector for processing. In SpMM, this gathers the relevant rows of the dense input matrix.
• Scatter: Writes data from a contiguous vector to a set of non-contiguous memory addresses. In SpMM, this scatters and accumulates partial results into the correct positions of the dense output matrix.

These operations are memory-bandwidth intensive and can cause load imbalance if not carefully managed, as different threads may handle varying numbers of non-zeros.

A specialized hardware unit in modern NVIDIA GPUs (e.g., Ampere, Ada Lovelace, Hopper architectures) designed to accelerate sparse matrix operations. It leverages a specific N:M Sparsity Pattern (e.g., 2:4), where in every block of 4 weights, 2 must be zero.

How it Works: The hardware reads a dense 4-value vector and a 4-bit mask. It prunes the 2 zero values on-the-fly and executes a dense matrix operation with the 2 non-zero values, effectively doubling the theoretical FLOPs throughput for eligible operations. This highlights the move from software-only sparse kernels to hardware-aware compression where the sparsity pattern is co-designed with the silicon.

A model compression technique that removes individual weights from a neural network based on a saliency criterion (e.g., magnitude-based pruning), resulting in irregular, fine-grained sparsity.

Relation to COO: The resulting weight tensors are perfect candidates for storage in the COO format, as the non-zero elements have no regular pattern. However, executing such models requires a sparse inference engine with kernels optimized for irregular access. The sparse efficiency gap is often more pronounced for unstructured sparsity compared to structured pruning due to higher sparse kernel overhead from metadata processing and irregular memory accesses.

The additional computational cost incurred when executing sparse operations versus their dense counterparts. This overhead can diminish the theoretical speedup gained from zero-skipping. Sources include:

• Metadata Processing: Reading and decoding index arrays (row, col in COO; row pointers in CSR).
• Irregular Memory Access: Non-contiguous gather-scatter operations cause poor cache utilization and high memory latency.
• Conditional Branching & Load Imbalance: Threads may follow different execution paths based on sparsity, leading to warp divergence on GPUs.

Optimizing a sparse inference engine involves minimizing this overhead through techniques like sparse operator fusion and choosing the optimal sparse data layout for the target operation.