elli-gf2

elli-gf2 is a small cross-language GF(2) elimination library with machine-first backends.

It currently provides four exact strategies:

• SparseList — human-semantic sparse sorted-list reduction
• PackedCached — packed-bitset sparse-friendly reduction
• DenseMacro — bit-packed dense macro-op reduction
• Auto — heuristic selector between backends

The current idea is simple:

different GF(2) workloads favor different machine-level execution shapes, so elli-gf2 chooses the best backend it knows rather than forcing one universal implementation.

What it can do today

• exact GF(2) elimination
• backend auto-selection
• generated workload benchmarking
• user-supplied sparse matrix files
• Rust library usage
• C ABI usage
• Python usage via ctypes

Quickstart

Rust library

use elli_gf2::{generate_er_sparse, reduce};

let rows = 2048;
let cols = generate_er_sparse(rows, 2048, 0.01, 1337);
let summary = reduce(rows, &cols);

println!("rank = {}", summary.rank);
println!("pivot_count = {}", summary.pivots.len());

CLI benchmark

cargo run --release --bin bench_cli -- --family er_sparse --rows 2048 --cols 2048 --density 0.01 --compare-all
cargo run --release --bin bench_cli -- --family ldpc_like --rows 2048 --cols 4096 --col-weight 6 --compare-all
cargo run --release --bin bench_cli -- --family banded --rows 2048 --cols 2048 --bandwidth 64 --weight 10 --compare-all

Load your own matrix

cargo run --release --bin load_cli -- --file examples/sample_matrix.txt --strategy auto

Matrix file format:

• first line: rows=<N>
• each following non-comment line is one column
• each column line is a whitespace-separated list of row indices
• empty lines count as empty columns
• comment lines begin with #

Example:

rows=8
0 2 4
1 4
2 3 7

0 7
1 2 5
3 6

Cross-language usage

C ABI

Header:

• include/elli_gf2.h

Example:

• examples/c_file_smoke.c

Build and run:

cargo build --release
clang -O3 examples/c_file_smoke.c -Iinclude -Ltarget/release -Wl,-rpath,"$PWD/target/release" -lelli_gf2 -o /tmp/elli_gf2_c_file_smoke
/tmp/elli_gf2_c_file_smoke

Python

Recommended setup:

python3 -m venv .venv
source .venv/bin/activate
cargo build --release
python -m pip install -e .
python examples/python_file_smoke.py

Example:

from elli_gf2 import reduce_file_auto

result = reduce_file_auto("examples/sample_matrix.txt")
print(result.rank, result.strategy, result.ok)

Current backend behavior

Observed selector behavior on representative families:

• er_sparse → DenseMacro
• ldpc_like → PackedCached
• banded → DenseMacro

This is intentional: elli-gf2 is a backend family plus selector, not a one-kernel-fits-all design.

Project layout

elli-gf2/
  Cargo.toml
  pyproject.toml
  README.md
  include/
    elli_gf2.h
  examples/
    c_file_smoke.c
    c_smoke.c
    python_file_smoke.py
    python_smoke.py
    rust_file_smoke.rs
    sample_matrix.txt
  python/
    elli_gf2/
      __init__.py
  scripts/
    share_smoke.sh
  src/
    lib.rs
    abi.rs
    io.rs
    bin/
      bench_cli.rs
      load_cli.rs
      smoke.rs

One-command repo smoke test

bash scripts/share_smoke.sh

Status

This is an early research-driven library, but it already provides:

• exact GF(2) elimination
• multiple machine-first backends
• automatic backend selection
• Rust, C, and Python entry points
• file-based input for user-supplied matrices