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.

The two outcomes of a certified screen are used differently.

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:

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:

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.

CommandWhat 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.pyRuns the whole self-test suite, sabotage controls included, from a temporary directory
battery.pyThe 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.

FunctionWhat 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

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.

ReferenceWhat it supplies
A. von Manteuffel and R. M. Schabinger, "A novel approach to integration by parts reduction", arXiv:1406.4513Integration-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.06494The finite-field methods of the Kira 2.0 program

← back to the tools index