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 WinnowSourceAuthors
Code that follows Kira's parser: the file search and the split into equations and terms in adapters/user_system.pysrc/kira/interface.cpp and src/pyred/integrals.cpp in KiraMaierhöfer, Usovitsch and Uwer; Klappert and Lange; Wu
New code that reads files Kira writes: adapters/kira.py and adapters/weights.pyThe SYSTEM_*.gz files and kira.db of a Kira 3.1 runFile 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.pyWritten for BootLoopsCode 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.

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.

Winnow has these limits:

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.

FunctionWhat 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

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.

ReferenceWhat it supplies
S. Laporta, hep-ph/0102033The elimination algorithm
P. Maierhöfer, J. Usovitsch and P. Uwer, Kira, arXiv:1705.05610; code: gitlab.com/kira-pyred/kiraKira, whose parser the equation-file reader follows
J. Klappert, F. Lange, P. Maierhöfer and J. Usovitsch, Kira 2.0, arXiv:2008.06494The user_defined_system file format
F. Lange, J. Usovitsch and Z. Wu, Kira 3, arXiv:2505.20197The version whose intermediate files the first adapter reads

← back to the tools index