Rankscreen
Rankscreen finds the rankthe dimension of the space spanned by the equations, the pivot positionsfor each equation that the elimination keeps, its row and the first column in which its reduced form is nonzero and the contradictory equations of a large linear system with exact rational coefficients, 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. Elimination modulo several primes is standard exact linear algebra, as in the finite-field reductions of Feynman integrals by von Manteuffel and Schabinger and by Klappert, Lange, Maierhöfer and Usovitsch (Kira 2.0).
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).
The screen has three steps.
- Map. Each coefficient $a/b$ becomes $a\,b^{-1} \bmod p$, for $k \ge 2$ primes at once.
- Eliminate. The elimination runs in machine integers, one process per prime.
- Compare. The rank, the full sequence of (pivot column, row) pairs, and the set of inconsistent rows are compared across the primes. Identical at every prime gives the verdict
CERTIFIED-SCREEN. Any difference givesESCALATE-TO-EXACT. No majority vote is taken, so two primes agreeing against a third still escalates.
The two outcomes of a certified screen are used differently.
- Refutation. A rank deficit or a nonempty inconsistent set is a refutation. The unanimous screen is the final answer, and the exact solve is skipped.
- Closure candidate. Full rank on the unknown columns (the first
nunk) with no inconsistent rows setsclosure_candidate: true, meaning the system may determine every unknown. Such a system must always go on to the exact rational elimination. The drop-ingauss_rank_screeneddoes this itself; after the command-line screen it is the user's job. The exact solve is 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}$.
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). With backend='auto' the dense backend is used 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.
Rankscreen has these limits:
- Verdicts follow the convention of the exact eliminator the screen stands in for. Rows are taken in the order given, each new row is reduced against existing pivot rows in creation order, and the pivot is 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.
- A wrong unanimous verdict needs every prime to divide a specific nonzero integer built from minors (subdeterminants) 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
--kor rerun with a disjoint--primeslist to shrink it.
Examples
Run the self-test suite. With the package set up (see Requirements), run from the root of the BootLoops repository; the package directory is tools/rankscreen/:
python3 tools/rankscreen/selftest.py
The script runs the whole suite, sabotage controls included, from a temporary directory. The four tests use synthetic systems from fixtures.py whose answers follow from their construction:
planted_control: a full-rank system with 48 known pivots, which the screen must reproduce.zero_eq_one: a system with three contradictory rows, which the screen must flag.prime_disagree: a row built so that the rank differs between two pool primes. The verdict must escalate, even at $k=3$ with two primes agreeing.bad_denominator: 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, and labels is a parallel list of names. 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. The test compares these with truth and with shim.gauss_rank_mpq on the same rows.
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. It then prints 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. With --backend auto such primes run on the sparse backend instead.
Routines
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.
| Command | What it does |
|---|---|
screen.py ROWS.json.gz [options] | Screens a rankscreen-rows-v1 file with --k primes in parallel; prints or saves the verdict |
selftest.py | Runs the whole self-test suite, sabotage controls included, from a temporary directory |
battery.py | The suite itself, with options --legs a,b, --mutation-controls, --summary-out F and --tool-dir D; run it outside the package directory |
The functions are imported with tools/rankscreen/ on sys.path.
| Function | What it returns |
|---|---|
screen.screen_rows(rows, labels, ncols, k, backend, primes, nunk, receipt_path) | The verdict dictionary, also written to receipt_path if given |
shim.screen_rows_labeled(rows_all, ncols, nunk, k, backend, receipt_path) | The same, for (label, coefficients, rhs) triples |
shim.gauss_rank_screened(rowlist, track_labels, ...) | The six items (rank, n_inconsistent, pivots, reduced_rows, reduced_rhs, inconsistent_labels) of an exact eliminator, for which it is a drop-in |
shim.exact_seeded(rowlist, track_labels, pivot_rows) | The same six items from an exact elimination that processes the predicted pivot rows first |
shim.gauss_rank_mpq(rowlist, track_labels) | The same six items from the reference exact rational eliminator (gmpy2), in the screen's convention |
shim.serialize_rows(rows_all, ncols, path) | The SHA-256 of the gzip JSON row file it writes |
shim.load_rows(path) | (rows, labels, ncols, meta) read from a row file |
modp_rref.rref_modp(rows, p, ncols, backend) | One elimination modulo p, as a ModpResult with fields rank, pivots, incon_idx, prime and backend |
The verdict dictionary always holds verdict, rank, n_inconsistent, primes, primes_replaced and a per_prime list with the rank, the inconsistent count and a pivot-sequence hash for each prime. When the primes agree it also holds closure_candidate and the agreed pivot_cols, pivot_rows and incon_idx, with incon_labels if labels were given. When primes disagree, rank and n_inconsistent are None and a disagreement list gives each prime's rank and inconsistent count.
gauss_rank_screened runs the seeded exact solve for a closure candidate (or, with force_exact=True, for any certified screen) and the plain exact solve when the primes disagree. Otherwise it returns the screened refutation with the reduced-row entries None. exact_seeded verifies the prediction and falls back to plain row order if it fails. The seeding is a cross-check of the screen and does not shorten the exact solve.
rref_modp_dense(rows, p, ncols) and rref_modp_sparse(rows, p, ncols) run one backend directly. modp_rref.py also defines BadPrime, the exception raised when p divides a denominator, which triggers the replacement. PRIMES_DENSE, PRIMES_SPARSE and DENSE_NCOLS_MAX hold the fixed pools and the dense column cap.
Requirements
- Runs on: Python 3 with numpy (dense backend) and gmpy2 (exact reference eliminator). Without gmpy2 the self-test suite falls back to
Fractionarithmetic. - Operating system: Linux or another Unix-like system. Parallel runs use
multiprocessingwith theforkstart method, so that workers share the rows without copying. - Install: no build step. Run the scripts from the repository root, or put
tools/rankscreen/onsys.pathto import the modules. - Self-test:
python3 selftest.pyin the package directory, or equivalentlypython3 tools/rankscreen/selftest.pyfrom the repository root. It ends with a line beginningOVERALL PASS. Exit code 0 means every test passed and every sabotage was caught. - Shared machines: run under
nice.
Source and references
The code is in tools/rankscreen/ in the BootLoops repository, released under the MIT license. GUIDE.md in that directory is the manual.
| Reference | What it supplies |
|---|---|
| A. von Manteuffel and R. M. Schabinger, "A novel approach to integration by parts reduction", arXiv:1406.4513 | Integration-by-parts reduction of Feynman integrals over finite fields |
| J. Klappert, F. Lange, P. Maierhöfer and J. Usovitsch, "Integral reduction with Kira 2.0 and finite field methods", arXiv:2008.06494 | The finite-field methods of the Kira 2.0 program |