Binary Representation of Sparse Matrices Using Bitsets

This article explains how the binary number system represents the structural patterns of sparse matrices using bit vectors and compressed bitset architectures. By decoupling matrix topology from numerical data, binary bit vectors map zero and non-zero states to single bits. Readers will learn the mechanics of uncompressed bit vectors, advanced compression techniques like Run-Length Encoding and Roaring Bitmaps, and how hardware-level bitwise operations optimize sparse linear algebra computations.

The Principle of Binary Sparsity Mapping

A sparse matrix consists predominantly of zero elements. Traditional sparse storage formats, such as Coordinate List (COO) or Compressed Sparse Row (CSR), store the explicit row and column indices of non-zero elements using 32-bit or 64-bit integers.

Binary representation optimizes this by stripping away numerical values and modeling only the matrix’s structural topology (the “sparsity pattern”). In this paradigm: * 1 represents the presence of a non-zero element. * 0 represents a zero element (absence of data).

The numerical values are stored in a contiguous, separate one-dimensional array. The binary representation serves as an index mask that maps each value in the array to its exact coordinates in the matrix.

Uncompressed Bit Vectors

An uncompressed bit vector represents a sparse matrix as a dense sequence of bits. A matrix of dimensions \(M \times N\) is flattened into a single bit vector of length \(M \times N\), or into \(M\) distinct bit vectors, each of length \(N\) representing a single row.

Original Matrix (4x4):
[ 5.0   0.0   0.0   2.1 ]
[ 0.0   0.0   0.0   0.0 ]
[ 0.0   8.4   0.0   0.0 ]
[ 1.2   0.0   0.0   3.7 ]

Row Bit Vectors:
Row 0: 1 0 0 1  (Hex: 0x9)
Row 1: 0 0 0 0  (Hex: 0x0)
Row 2: 0 1 0 0  (Hex: 0x4)
Row 3: 1 0 0 1  (Hex: 0x9)

Flattened Vector (16 bits):
1001 0000 0100 1001

Values Array:
[ 5.0, 2.1, 8.4, 1.2, 3.7 ]

Memory Efficiency

Compared to dense storage (which requires 32 or 64 bits per element regardless of value), a bit vector uses exactly 1 bit per entry. Compared to CSR, an uncompressed bit vector is more memory-efficient when the matrix density exceeds roughly 1% to 3%, depending on the architecture’s pointer size.

Compressed Bitsets

When matrices scale into millions of rows and columns with densities below 0.01%, uncompressed bit vectors waste substantial memory storing long sequences of 0 bits. Compressed bitset algorithms compress these binary streams without losing the ability to perform fast indexing.

1. Word-Aligned Hybrid (WAH) and Run-Length Encoding (RLE)

Run-Length Encoding compresses long sequences of identical bits into pairs: the bit value and its repeat count. Word-Aligned Hybrid (WAH) encoding adapts RLE to machine-word boundaries (32-bit or 64-bit words). A word’s most significant bit indicates whether the word contains: * A Literal Word: The remaining 31 or 63 bits are raw bit patterns. * A Fill Word: The word encodes a run of consecutive 0s or 1s, storing the length of the run.

This allows entire blocks of empty matrix space to be represented by a single machine word.

2. Roaring Bitmaps

Roaring Bitmaps partition the 32-bit integer index space into chunks of \(2^{16}\) (65,536) integers based on the most significant 16 bits. The least significant 16 bits are stored in one of three container types depending on local density: * Array Container: Used when a chunk contains fewer than 4,096 non-zero entries. Stores raw 16-bit indices. * Bitset Container: Used when a chunk contains between 4,096 and 61,440 entries. Stores a fixed 8 KB uncompressed bitset (65,536 bits). * Run Container: Used when entries form contiguous sequences. Stores run-length encoded start and length pairs.

This dynamic partitioning ensures optimal space and retrieval speeds across heterogeneous sparsity distributions.

Arithmetic and Algorithmic Operations

Binary representation allows sparse matrix operations to leverage low-level CPU instructions:

Logical Intersections and Unions

• Matrix Addition Structure: The non-zero pattern of \(A + B\) is computed using a bitwise OR between the bitsets of \(A\) and \(B\).
• Hadamard (Element-Wise) Product: The pattern of \(A \circ B\) is computed using a bitwise AND.
• Matrix Subtraction Structure: The pattern is resolved using a bitwise XOR or OR.

Because these operations run on 64-bit words or 256/512-bit SIMD registers (AVX-512), the CPU processes 64 to 512 matrix cells in a single clock cycle.

Fast Index Calculation via Hardware Instructions

To map a bit to its corresponding position in the dense numerical values array, processors use dedicated instructions: * Population Count (popcount): Computes the total number of set bits (1s) before a specific position. The result yields the exact offset index in the numerical values array. * Count Trailing Zeros (ctz / clz): Quickly finds the next non-zero column index without scanning every intermediate 0 bit individually.

Combining bitsets with hardware-accelerated instructions minimizes memory bandwidth bottlenecks and accelerates structural operations in sparse matrix computation.