Rankscreen

The content on this page was written by AI under human supervision.

Rankscreen finds the structure of a large linear system with exact rational coefficients (its rank, its pivot positions, and which equations contradict the rest) without doing exact arithmetic. It repeats the Gaussian elimination modulo several primes in parallel, one process per prime, and accepts the answer only when every prime gives the identical result; any disagreement sends the system to the exact solver. Input is a list of sparse rows with Fraction coefficients, in memory or as a gzip JSON file; output is a verdict dictionary, optionally saved as JSON.

What it does

Exact Gaussian elimination on thousands of rows and columns is slow because numerators and denominators grow as it runs. Often only the structure is wanted: whether the rank is full on the unknowns, and whether any row reduces to $0 = c$ with $c \neq 0$ (an inconsistent row). Rankscreen maps each coefficient $a/b$ to $a\,b^{-1} \bmod p$ and runs the elimination in machine integers for $k \ge 2$ primes at once. It then compares the rank, the full sequence of (pivot column, row) pairs, and the set of inconsistent rows across the primes. Identical at every prime gives the verdict CERTIFIED-SCREEN. Any difference gives ESCALATE-TO-EXACT; there is no majority vote, so two primes agreeing against a third still escalates.

The two outcomes are used differently. A rank deficit or a nonempty inconsistent set is a refutation, and the unanimous screen is the final answer; the exact solve is skipped. Full rank on the unknown columns (the first nunk) with no inconsistent rows sets closure_candidate: true, meaning the system may determine every unknown. Such a system must always go on to the exact rational elimination (the drop-in gauss_rank_screened does this itself; after the command-line screen it is the user's job), seeded with the agreed pivot rows, with a fallback to plain row order if the prediction fails. Rank can drop modulo a prime but never rise, so full rank at even one prime already proves full rank over $\mathbb{Q}$.

Verdicts follow the convention of the exact eliminator the screen stands in for: rows in the order given, each new row reduced against existing pivot rows in creation order, pivot at the smallest nonzero column of the reduced row. Which row of a dependent group gets flagged depends on row order, so compare verdicts only between identically ordered inputs. Rankscreen returns no solution vector and, on the refutation branch, no reduced rows; it is not a general sparse linear-algebra library.

Two backends give identical verdicts: dense (numpy int64, primes below $2^{25}$, at most 8192 columns) and sparse (Python integers, 30-bit primes, less memory); backend='auto' picks dense when the caps allow. Primes come from two fixed pools of sixteen, so reruns are reproducible. A prime that divides some denominator cannot represent the system: it is replaced by the next pool prime and the swap is listed under primes_replaced; if the pool runs out, the call stops with an error. A wrong unanimous verdict needs every prime to divide a specific nonzero integer built from minors of the system and to give the same wrong output. Because closure candidates always get the exact solve, the only exposure is a false refutation; raise --k or rerun with a disjoint --primes list to shrink it.

Examples

Run the self-test suite. From the root of BootLoops' bootloops-dev repository (GitHub organization BootLoops-ai):

python3 tools/rankscreen/selftest.py

The script runs the whole suite, sabotage controls included, from a temporary directory on four synthetic systems from fixtures.py whose answers follow from their construction. Two have a known answer the screen must reproduce: a full-rank system with 48 known pivots, and one with three contradictory rows. The other two test the safeguards: a row that two pool primes rank differently (the verdict must escalate, even at $k=3$ with two primes agreeing), and a coefficient whose denominator is divisible by a pool prime. The suite then copies the tool aside, breaks one mechanism per test, and requires exactly that test to fail. Expect four PASS <test> lines, four MUTATION <test>: CAUGHT lines, a summary -> line with the report JSON path, and OVERALL PASS (4 legs + 4 mutation controls, ...) with exit code 0, within a few seconds.

Screen a system from Python. The call the first test makes, with tools/rankscreen/ on sys.path:

import fixtures, screen
rows, labels, ncols, nunk, truth = fixtures.planted_control()
v = screen.screen_rows(rows, labels, ncols, k=2, backend="dense",
                       nunk=nunk, tag="battery-dense")

rows is a list of ({column: Fraction}, Fraction) pairs, one per equation, labels a parallel list of names, and nunk=48 marks the first 48 of the 64 columns as the unknowns for the closure flag. v comes back with verdict 'CERTIFIED-SCREEN', rank 48, n_inconsistent 0, closure_candidate True, primes [33554393, 33554383] and primes_replaced empty. It also carries the agreed pivot_cols and pivot_rows, incon_idx, incon_labels, a per_prime list (rank, inconsistent count, pivot-sequence hash, seconds for each prime) and wall_secs. The test compares these with truth and with shim.gauss_rank_mpq on the same rows. When primes disagree, rank is None and a disagreement list gives each prime's rank and inconsistent count.

Screen a saved system from the command line. The usage line from the guide:

python3 tools/rankscreen/screen.py ROWS.json.gz [--k 2] [--backend auto|dense|sparse] [--nunk N] [--out RECEIPT.json] [--primes p1,p2,...] [--tag t]

ROWS.json.gz is the rankscreen-rows-v1 file that shim.serialize_rows(rows_all, ncols, path) writes from (label, {column: Fraction}, Fraction) triples. The script prints the verdict as JSON without the long pivot lists, then one line of the form VERDICT: CERTIFIED-SCREEN rank R/ncols inc N closure_candidate=..., or VERDICT: ESCALATE-TO-EXACT with a note to run the exact solve. --out saves the full dictionary, including the pivot and inconsistent-row lists and a SHA-256 of the input file. With --backend dense, a --primes value of $2^{25}$ or more raises an error rather than overflowing; --backend auto runs such primes on the sparse backend instead.

Routines

Command line

Screening (screen.py, shim.py)

One prime at a time (modp_rref.py)

Test fixtures (fixtures.py)

Requirements and source

Python 3 with numpy (dense backend) and gmpy2 (exact reference eliminator; the self-test suite falls back to Fraction arithmetic without it). Parallel runs use multiprocessing with the fork start method so workers share the rows without copying, which needs Linux or another Unix-like system; on a shared machine run under nice. Self-tests: python3 selftest.py in the package directory (equivalently python3 tools/rankscreen/selftest.py from the repository root); exit code 0 means every test passed and every sabotage was caught. The code is in tools/rankscreen/ in the bootloops-dev repository, released under the MIT license, with GUIDE.md there as the manual.

← back to the tools index