Introduction

For sparse boolean matrices, the fastest representation depends on the shape of your data and the multiplication pattern. If the matrix is truly sparse, the best representation usually stores only the positions of true values. If it is only moderately sparse, bitsets can outperform sparse structures by using fast word-level operations.

The biggest optimization comes from remembering that boolean matrix multiplication uses the boolean semiring: multiplication becomes logical and, and addition becomes logical or. Because the values are only true or false, you can skip storing numeric payloads and stop work as soon as you know one output entry is true.

Good Representations for Sparse Boolean Data

The standard sparse formats still apply:

• CSR, or compressed sparse row, is excellent when you scan rows often.
• CSC, or compressed sparse column, is excellent when you scan columns often.
• Row sets, meaning one set of column indices per row, are simple and often very effective for boolean data.

For boolean matrices, row sets are conceptually close to an adjacency-list graph representation. A row does not need stored values because every stored position means true.

For example, this matrix:

1 0 1 0
0 0 0 0
0 1 0 1

can be stored as:

1rows = [
2    {0, 2},
3    set(),
4    {1, 3},
5]

That is compact, easy to work with, and often fast enough for highly sparse boolean data.

A Fast Multiplication Idea for Boolean Matrices

Suppose A and B are boolean matrices. To compute row i of the result, you only need to look at the columns k where A[i, k] is true. For each such k, union in row k of B.

That means if both matrices are represented as row sets, multiplication can be written very naturally:

1def boolean_matmul(a_rows, b_rows):
2    result = []
3
4    for active_columns in a_rows:
5        out_row = set()
6        for k in active_columns:
7            out_row.update(b_rows[k])
8        result.append(out_row)
9
10    return result
11
12
13A = [
14    {1, 3},
15    {0},
16]
17
18B = [
19    {2},
20    {0, 2},
21    set(),
22    {1},
23]
24
25print(boolean_matmul(A, B))

This works because boolean multiplication only asks whether there exists at least one connecting index. We do not need to add counts or multiply stored numeric values.

When CSR and CSC Are Better

For large production workloads, specialized sparse formats such as CSR for A and CSC for B are often better than plain Python sets. They reduce memory overhead and improve cache locality.

A common strategy is:

• Store the left matrix in CSR so rows are cheap to iterate.
• Store the right matrix in CSC if you need efficient column access.
• Intersect row and column index lists, or use sparse matrix multiplication kernels optimized for these layouts.

If you are using a numerical computing library, that library can usually do this much faster than custom Python loops once the data size grows.

When Bitsets Win

If the matrices are not extremely sparse, bitsets become attractive. Each row can be stored as packed machine words, and multiplication checks can use fast bitwise and instructions.

Conceptually, for one output cell:

def any_overlap(row_bits, col_bits):
    return (row_bits & col_bits) != 0

At scale, vectorized bit operations can beat pointer-heavy sparse structures, especially when rows have enough true values that sparse traversals stop being cheap.

Choosing the Fastest Approach

Use row sets or CSR-like storage when:

• The matrix is very sparse.
• You mostly iterate active positions.
• Simplicity matters and the dataset fits the approach.

Use bitsets when:

• Density is moderate rather than extremely sparse.
• Dimensions are large and fixed.
• You can benefit from CPU word-level parallelism.

Use a tuned sparse linear algebra library when:

• Multiplication is a bottleneck.
• Data sizes are large.
• You need predictable performance and memory behavior.

Common Pitfalls

The biggest mistake is storing sparse boolean matrices as dense two-dimensional arrays. That wastes memory and destroys the performance benefits of sparsity.

Another problem is carrying around explicit numeric 1 values even though the matrix is boolean. In many applications, storing only indices is enough.

It is also easy to choose a representation that is optimal for construction but poor for multiplication. If you multiply often, choose a layout optimized for traversal, not just easy insertion.

Finally, do not assume "sparse" automatically means CSR is fastest. Once density rises, bitsets or blocked representations may win.

Summary

• For truly sparse boolean matrices, store only the positions of true values.
• Row sets and CSR-style layouts are strong defaults for sparse multiplication.
• Boolean multiplication can short-circuit and use set union instead of numeric accumulation.
• Bitsets often outperform sparse structures when the matrix is only moderately sparse.
• The fastest approach depends on sparsity, matrix shape, and whether multiplication is the dominant operation.