Winnow
Winnow is a Python library for the elimination step of integration-by-parts (IBP) reductionwriting the thousands or millions of Feynman integrals of one family through a few master integrals, by means of linear relations obtained from integrating a total derivative, carried out by Laporta's algorithm (hep-ph/0102033) modulo a prime at one numerical kinematic point. You give it the sparse linear identities, an elimination order and the columns that stand for master integrals. It returns every eliminated integral written in terms of the masters, a certificate for each requested row that can be checked without the solver, and a JSON log of the run.
Where it comes from
Kira is the reduction program of P. Maierhöfer, J. Usovitsch, P. Uwer, J. Klappert, F. Lange and Z. Wu, and the two file formats that Winnow reads are theirs. Winnow's reader for Kira's user_defined_system equation files follows Kira's parser. It reproduces five rules of that parser that the Kira documentation does not state, and one of its error messages is Kira's, word for word. The elimination engine and the certificates were written for BootLoops.
Certificates requested after the elimination are computed with Wiedemann's algorithm (a solver for sparse linear systems over $\mathbb F_p$), with Berlekamp-Massey and Kaltofen-Saunders preconditioning.
| Part of Winnow | Source | Authors |
|---|---|---|
Code that follows Kira's parser: the file search and the split into equations and terms in adapters/user_system.py | src/kira/interface.cpp and src/pyred/integrals.cpp in Kira | Maierhöfer, Usovitsch and Uwer; Klappert and Lange; Wu |
New code that reads files Kira writes: adapters/kira.py and adapters/weights.py | The SYSTEM_*.gz files and kira.db of a Kira 3.1 run | File format by the same authors; code by Claude |
New code: the elimination engine, the certificates, the run log and the rest of adapters/user_system.py | Written for BootLoops | Code by Claude |
Please cite the Kira papers listed under Source and references when you use either adapter. Winnow is not affiliated with or endorsed by the Kira developers.
What it does
A multi-loop Feynman-integral calculation produces a large, sparse linear system, the IBP identities. Laporta's algorithm solves it by Gaussian elimination in a fixed order, most complicated integrals first. Reduction programs such as Kira do this in a prime field $\mathbb F_p$ at numerical values of the dimension and the invariants and reconstruct the rational coefficients from many samples. Winnow is that one elimination as a library with a fixed contract.
In Winnow a column is an integer with no meaning attached. The physics enters through three dictionaries.
- Order.
orderranks the columns; a higher rank is eliminated first. - Masters.
forbidlists the master columns, which are never used as pivots. - Blocks.
stratum_of, which is optional, groups the columns into blocks solved one after another, highest stratum first.
The call is eliminate(System, Schedule). In the result, subs maps each pivot column $t$ to a closed row $r$ over master columns only, with the convention $I_t + \sum_m r[m]\, I_m = 0 \pmod p$. Relations among the masters themselves (a redundant basis or a rank-deficient system) come back in leftover and are never dropped. The four pivot policies B2, B3, B2F and B2FT give identical answers and differ only in fill-in (the new nonzero entries that elimination creates) and cost.
For any pivot listed in witness_targets, witnesses="retrofit" produces a certificate: sparse multipliers $\lambda_i$ over the input rows $R_i$ and the claimed master coefficients $c_m$ such that
$$\sum_i \lambda_i\, R_i \;=\; e_t - \sum_m c_m\, e_m \pmod p .$$
If the identity holds, the row $I_t=\sum_m c_m I_m$ is an exact linear consequence of the input system at that point and prime, whatever code produced it. The check is exact integer arithmetic with no tolerance. The checker, ibplapper.receipt, imports nothing from the solver and is meant to be run against your own parse of the input rows. The package's README records a reduction table that had full rank and agreed at two primes and was wrong; only the certificate check rejected it.
Two adapters build a System from files on disk.
- Kira's intermediate files. Run Kira with
run_initiate: true(generate and select the identities, no back-substitution).adapters.kira.loadthen turns theSYSTEM_*.gzfiles into aSystem, with masters forbidden and each column's stratum set to the number of propagators in its sector (the set of propagators with positive power). - Equation files.
adapters.user_system.loadreads equation files in Kira's documenteduser_defined_systeminput format: oneintegral*coefficientterm per line, blank lines between equations, integer weights orname[indices]labels, plain or gzipped. The reader follows Kira's parser (see Where it comes from) and needs no Kira installation or version check. You pass the numerical value of every symbol in the coefficients; an undeclared symbol stops the load with an error. Withname[indices]labels the adapter assigns standard Laporta ranks and propagator-count strata, which you may override.
Winnow has these limits:
- Scope. Winnow does not generate identities, apply sector symmetries, choose the ordering, combine primes by Chinese remaindering or reconstruct rational functions. That stays with the caller. Nothing is written back into Kira.
- Certificates. A certificate holds at one kinematic point and one prime. It does not show that a symbolic table is right, or that the input system itself was correct or complete.
- Size. The default engine is pure Python on dictionary rows. The largest system measured had about 454,000 equations and needed roughly 20 GB per numerical point. An optional dense backend (
backend="dense", PyTorch, policiesB2F/B2FT, $p \lt 2^{31}$) reproduces the default output exactly. - Retrofit certificates. They are solved for after the elimination, so estimate the cost of a large batch before requesting one.
- Native certificates.
witnesses="native"records the multipliers during the elimination, with no solve afterwards. It runs withB2F/B2FTon the default backend only;B2,B3andbackend="dense"raiseNotImplementedError. The tracking adds fill, and each run writes its measured cost intoledger["witnesses"]["transcript_fill"]. - Kira versions.
SYSTEM_*.gzis an undocumented internal Kira format that the adapter decodes empirically. The decode was validated for Kira 3.1 (kira.dbversion 2.1, integral ordering 5). The adapter refuses other packing constants (KiraVersionError) and recordsABSENT-UNGUARDEDwhenkira.dbis missing. - Master labels. Kira does not export its weight-to-integral dictionary. The readable master labels that the adapter attaches are best effort and must be confirmed by the certificate check.
Seedling uses Winnow as its elimination engine. The checker ibplapper.receipt is a byte-identical copy of the receipt module of Trust. In both certificate modes the certificate is verified through it before it is returned.
Examples
A three-identity system with certificates. Columns 201 to 203 are integrals to eliminate, and 101 and 102 are masters. The snippet is the untampered case of the package's tamper test tests/test_sabotage.py, with OUT a scratch directory. Run it with the package directory tools/winnow/ on the Python path (see Requirements):
import os
import ibplapper as lap
P = 2147483647
ROWS = [{203: 1, 101: (-5) % P},
{202: 1, 203: (-3) % P, 102: (-7) % P},
{201: 1, 202: (-2) % P, 101: (-1) % P}]
sys_ = lap.System(ROWS, P, {201: 3, 202: 2, 203: 1}, forbid={101, 102})
res = lap.eliminate(sys_, lap.Schedule(policy="B2FT"), witnesses="retrofit",
witness_targets=[201, 202, 203],
witness_dir=os.path.join(OUT, "wits"))
res.subs[202] is {101: P-15, 102: P-7}, that is $I_{202} = 15\,I_{101} + 7\,I_{102}$. Likewise $I_{203}=5\,I_{101}$ and $I_{201}=31\,I_{101}+14\,I_{102}$, and res.leftover is empty. Each res.witnesses[t] records the certified coefficients c ({101: 15, 102: 7} for 202), status "CERTIFIED", verify_pass True, the nonzero multipliers lam, and witness_path, here OUT/wits/w_2147483647_202.json.
To check a certificate later against rows you parsed yourself (README):
from ibplapper import receipt ok, detail = receipt.verify(my_own_rows_parse, "w_2147483647_....json")
ok is True only on an exact match. Otherwise detail["reason"] names the failure (identity failed, row count differs, fingerprint mismatch).
Catching a tampered certificate or a wrong table. Continuing the first example (the package's GUIDE.md repeats the check with the Python standard library alone):
from ibplapper import receipt
wit = receipt.load_witness(res.witnesses[202]["witness_path"])
receipt.verify_row(ROWS, wit) # (True, {...})
receipt.verify_row(ROWS, wit, table_row={101: 16, 102: 7}) # (False, {...})
The first call passes. The second is rejected although the certificate is valid, because the table row claims different coefficients: the reason is "claimed table row != certified row (witness holds; the TABLE is wrong)" and first_diff_col is 101. A copy of the certificate with its coefficients changed to {101: 30, 102: 14} fails with reason "identity failed: residual != e_t - sum c_m e_m".
Behind Kira, or from equation files. After a Kira run with run_initiate: true, load the generated system at one numerical point and one prime (one slice) and eliminate it (README quickstart):
from ibplapper.adapters import kira
system, sysd = kira.load(art_dir, family, p, d0, eta0,
expect_counters={"eqs": 7135, "terms": 42286})
res = lap.eliminate(system, lap.Schedule(policy="B2FT"))
art_dir is the Kira working directory (with tmp/<family>/SYSTEM_*.gz, results/<family>/masters, sectormappings/); d0 and eta0 are the integers at which $d$ and the auxiliary parameter $\eta$ are evaluated modulo p. expect_counters is optional: if the loaded equation and term counts differ from the declared ones, load raises ProvenanceError. res.subs is keyed by Kira's integer weights; a relation among Kira's declared masters would appear in res.leftover. sysd holds the adapter's record: counters (with the version_guard entry), masters and sector_of.
Without Kira, the same kind of slice loads from equation files in the user_defined_system format (README quickstart):
from ibplapper.adapters import user_system
system, sysd = user_system.load(
"eqs/", p, values={"d": d0, "s": s0, "m2": m20}, # one numeric slice
forbid=[("T", (1, 0, 0))], # masters, by label
expect_counters={"eqs": 7135, "terms": 42286})
res = lap.eliminate(system, lap.Schedule(policy="B2FT"))
eqs/ is a file or a directory of .kira/.kira.gz files, and forbid takes (family, indices) labels or raw column ids. sysd["labels"] maps each column back to its integral, so res.subs can be read as reduction rules. A downstream check re-parses the same files and calls receipt.verify, as for every route.
Routines
The package imports as ibplapper (import ibplapper as lap); import winnow is an alias.
| Function | What it returns |
|---|---|
System(rows, p, order, forbid, stratum_of, meta) | The input; a column that is both ranked and forbidden is refused |
Schedule(policy, bank, caps) | The pivot policy, with an optional Bank and optional caps |
eliminate(system, schedule, witnesses, witness_targets, witness_dir, backend) | A Result with subs, leftover, witnesses and ledger |
Bank(base) | An append-only table of reduced blocks on disk |
receipt.verify(rows, witness, table_row) | (ok, detail) for one certificate, a dict or a file path; with table_row, a claimed table row is compared too |
receipt.verify_row(rows, wit, table_row) | The same check on a certificate already loaded as a dict |
receipt.verify_many(rows, witnesses, table) | (rc, report) for a batch; rc is 0 if all pass, 1 on any failure, 2 if nothing valid was found |
receipt.load_witness(path) | The version 1.0 certificate JSON as a dict; an unreadable or incomplete file raises receipt.MalformedInput |
adapters.kira.load(art_dir, family, p, d0, eta0, expect_counters, m20) | (System, sysd) from a Kira working directory; m20 is the value of a mass squared m2 |
adapters.user_system.load(src, p, values, forbid, expect_counters) | (System, sysd) from equation files in the user_defined_system format |
res.ledger holds the prime, the policy, a SHA-256 fingerprint of the input rows, per-stratum statistics and a witness summary. res.save_ledger(path) appends it to a file as one JSON line. A Bank stores each block's reduced rows under a key, refuses to overwrite a key and verifies a SHA-256 checksum on every read.
A Schedule may carry caps (stratum_wall_s, total_wall_s, stratum_fill), checked at the end of each block. When one is exceeded the run raises CensoredError with the partial log attached instead of returning a truncated table. adapters.user_system.load raises UserSystemFormatError on a malformed line, mixed notations or an undeclared symbol.
The lower-level modules (engine, coverage, certify, witness, backends) are listed in the Layout section of the package's README.md.
Requirements
- Runs on: Python 3.10 or newer with NumPy.
- Install: the repository has no installer. Run
git clone https://github.com/BootLoops-ai/bootloopsand put itstools/winnow/directory onPYTHONPATH. - Self-test:
tests/run_tests.sh [scratch_dir]ends withibplapper battery: ALL SUITES PASSand exits nonzero on any failure. It needspython-flint. The suites that need only this package run as is. Those that replay archived Kira systems printSKIPunlessWINNOW_BANKED_ROOTandWINNOW_T1_ROOTpoint at the files. - Optional:
python-flintfor the tests only (a separate dense row reduction to compare against), and PyTorch forbackend="dense"only.
Source and references
The code is tools/winnow/ in the BootLoops repository. The checker under ibplapper/receipt/ is a verbatim copy of the checker modules in tools/trust/receipt/ (core.py, emitter.py, detector.py), and a test enforces that the copies stay identical.
| Reference | What it supplies |
|---|---|
| S. Laporta, hep-ph/0102033 | The elimination algorithm |
| P. Maierhöfer, J. Usovitsch and P. Uwer, Kira, arXiv:1705.05610; code: gitlab.com/kira-pyred/kira | Kira, whose parser the equation-file reader follows |
| J. Klappert, F. Lange, P. Maierhöfer and J. Usovitsch, Kira 2.0, arXiv:2008.06494 | The user_defined_system file format |
| F. Lange, J. Usovitsch and Z. Wu, Kira 3, arXiv:2505.20197 | The version whose intermediate files the first adapter reads |