Ratfit
Ratfit recovers an exact rational function of one variable (a ratio of two polynomials with rational coefficients) from exact values at rational sample points, and confirms it on samples kept out of the fit. It uses Thiele's continued-fraction interpolationa classical way to interpolate a rational function through sample points one at a time, without solving a linear system for the coefficients, with the stopping test and the modular arithmetic that Peraro (arXiv:1608.01902) and Klappert, Klein and Lange (FireFly, arXiv:1904.00009, arXiv:2004.01463) made standard for amplitude calculations. It also designs sample grids, checks new samples against a reconstructed function, classifies stalled reconstructions modulo primes, and gives closed forms for a class of logarithmic integrals.
What it does
Differential equations for Feynman integrals are built from integration-by-parts reduction (the linear relations that reduce every integral of a family to a few master integrals). Each entry of their coefficient matrix is a rational function of the variable $t$ along the chosen kinematic path. A reduction run returns only the value of an entry at one numeric point. Ratfit takes sample points xs and values ys (Python Fractions) and returns numerator and denominator as exact flint.fmpq_poly polynomials. Everything runs in exact rational arithmetic; nothing here is a floating-point fit.
The package has these parts.
- Blind fit.
thiele_loobuilds a Thiele continued fraction through most of the samples and keeps six evenly spaced samples out. It reports success only if the result reproduces every sample exactly. - Known denominator. When the denominator is already known, for example from a lower order in the dimensional-regularization parameter $\varepsilon$,
ratrecon_with_denomfits the numerator alone and reaches higher degree. Candidate denominators are built from ones already validated in the same run and screened modulo a 61-bit prime before the exact test, which still follows every pass. - Grid. On a straight path between two kinematic points, parametrized by $t\in(0,1)$, two invariants coincide at certain rational values of $t$. A reduction there finishes normally and is reproducible, but it belongs to a degenerate configuration and spoils every fit that uses it, with no error message.
coincidence_locilists those values exactly.design_gridreturns fresh rational points that avoid them, avoid a user-supplied list of poles, and never repeat a point already used. - Check. The
thiele_gatesubmodule fits every entry of a matrix, sampled at trusted points, as a continued fraction that must reproduce the trusted samples not used in the fit. It then accepts a new, untrusted sample only if it lies exactly on the reconstructed function. A sample from a wrong configuration or a corrupted file has a negligible chance of passing. - Triage. The
degree_aliassubmodule serves reconstructions done modulo primes. There the function is sampled on a grid, fitted at several primes, and each coefficient is lifted to an exact fraction with the Chinese remainder theorem. When some entries will not lift, either the combined modulus is too small for the coefficients, and one more prime is the fix, or the grid has too few points on one axis. An aliased fit returns the same wrong function at every prime, and only more points on that axis help.classifysays which. - Closed forms. The
li2closesubmodule takes a list of "atoms", each standing for $\int_{lo}^{hi} c\,\ln\lvert P_0+P_1t\rvert\,/\,(W_0+W_1t)\,dt$ with coefficients rational or rational in one symbolic parameter, where $lo$ may be $0$ and $hi$ may be $\infty$. It returns the sum in closed form in the real dilogarithm $\mathrm{Re}\,\mathrm{Li}_2$ and products of logarithms, with the endpoint divergences kept as symbols $\ln\epsilon$ and $\ln\Lambda$.
Ratfit has these limits:
- From $n$ samples a blind fit resolves numerator and denominator degrees up to about $(n-6)/2$ each, and a known-denominator fit reaches numerator degree $n-8$.
degree_budgetreports these limits before any reduction is run. - Fits that fail at the degree limit need more samples or a known denominator. Fits that fail below it usually mean a bad sample point.
- Ratfit reconstructs rational functions of one variable.
parametric_rec_interpadds exact polynomial dependence on extra parameters for the coefficients of a sampled recurrence, and Numkin builds two-variable reconstructions on top of Ratfit. degree_aliasnames the axis and does not perform the extension, and it should be given failing entries only. Before acting on a verdict, run it on entries from the same computation that already lifted, where the answer is known.- In
li2closeevery divergent coefficient must cancel across the sum. If one survives,close_atomsraisesDivergenceError, because an incomplete atom list is a wrong answer. It does not check that a denominator root inside an atom's range cancels between atoms; that remains the caller's job.
Vopclose calls Ratfit for its exact entry reconstruction, and the sampled reductions typically come from Kira, FireFly and Fermat.
Examples
Reconstruct a rational function from 24 samples. The package's test samples $f=(3-2x+x^2)/(1+5x^2+7x^3)$ at $x=k/97$ and recovers it with and without the denominator. To run it, set up the package directory tools/ratfit/ first (see Requirements).
from fractions import Fraction
import flint
import ratfit
P_TRUE = flint.fmpq_poly([3, -2, 1])
Q_TRUE = flint.fmpq_poly([1, 0, 5, 7])
N_NODES = 24
XS = [Fraction(k, 97) for k in range(1, N_NODES + 1)]
def frac(v):
return Fraction(int(v.p), int(v.q))
def feval(x):
xq = ratfit.fq(x)
return frac(P_TRUE(xq) / Q_TRUE(xq))
YS = [feval(x) for x in XS]
P, Q, ok, deg = ratfit.thiele_loo(XS, YS)
Pn, Qd, ok, deg = ratfit.ratrecon_with_denom(XS, YS, Q_TRUE)
assert ratfit.screen_modp(XS, YS, Q_TRUE) is True
Each fit returns numerator and denominator as fmpq_poly objects (ascending coefficients), a flag ok that is True only when the kept-out samples were reproduced exactly, and the degree. Here both give ok true and deg == 3, with str(Pn) == str(P_TRUE).
Adding 1 to ys[2] makes both blind routes return ok false, and screen_modp with the wrong cubic flint.fmpq_poly([2, 3, 1, 1]) returns False.
Design a sample grid on a kinematic path. For the straight path between two five-point configurations used in the tests, list the degenerate values of $t$, then ask for 30 fresh points that also avoid a known pole and two points sampled earlier.
from fractions import Fraction
from ratfit import coincidence_loci, design_grid
PA = dict(s12=-3, s23=-5, s34=-7, s45=-2, s15=-11, mm=1)
PB = dict(s12=-3, s23=-5, s34=-7, s45=-11, s15=-17, mm=2)
loci = coincidence_loci(PA, PB)
grid = design_grid(PA, PB, 30, exclude=("1/2", Fraction(7, 60)),
poles=("11/60",))
loci is keyed by exact fractions: on this path $s_{45}$ equals $s_{12}$, $s_{23}$ and $s_{34}$ at $t=1/9$, $1/3$ and $5/9$. grid is a list of 30 entries {"t": "p/q", "checked": ["no-coincidence", "no-pole", "fresh"]} drawn from $k/60$, $k/120$ and $k/240$, none equal to a locus, to $11/60$, or to an excluded point. Asking for more than the denominators can supply, design_grid(PA, PB, 6, denominators=(9,)), raises ValueError ("only 5/6 admissible t values ...") instead of returning five points.
Put a logarithmic integral in closed form and check that its divergences cancel. $\int_0^\infty \ln(1+t)\,/\,(t(1+t))\,dt=\pi^2/6$; after partial fractions it is two atoms, each divergent like $\ln^2\Lambda$ on its own.
import sympy as sp
from sympy import oo
import li2close as lc
atoms = [lc.Atom(1, 0, 1, 1, 1, 0, oo, 'pf.t'),
lc.Atom(-1, 1, 1, 1, 1, 0, oo, 'pf.1pt')]
cl = lc.close_atoms(atoms)
f = lc.emitted_function(lc.emit_mpmath(cl.finite, 'val'), 'val')
Atom(c, W0, W1, P0, P1, lo, hi, tag) gives the coefficient, the denominator $W_0+W_1t$, the logarithm's argument $P_0+P_1t$ and the range. cl.finite is a sympy expression satisfying sp.simplify(cl.finite - sp.pi**2/6) == 0, and cl.ledger records the 'LE^0 LL^2' term with a verdict field showing it canceled. f(dps=50), compiled from the mpmath source that emit_mpmath writes, agrees with $\pi^2/6$ to at least 45 digits.
Passing only the first atom raises DivergenceError. Atoms that depend on a sympy symbol u need close_atoms(atoms, param=u, domain=(0, 1)).
Decide between another prime and a larger grid. Five coefficients on a $(50,100)$ grid refuse to lift; each was fitted at seven primes with the same degrees. The call is the first case of the submodule's self-test:
from ratfit.degree_alias import classify r = classify((50, 100), [[((49, 99), (0, 0))] * 7] * 5)
Each inner list is one failing entry, each tuple one prime's fit as ((num_d, num_e), (den_d, den_e)). Here every numerator sits at the ceiling $(49, 99)$ over a trivial denominator, so r['verdict'] is 'ALIAS' and r['axis'] is 'd' (both axes are pinned and ties go to d). r['counts'] gives the breakdown, with n_fits and alias both 5.
Three entries on a $(29,101)$ grid with fits such as ((12, 46), (9, 47)) repeated at five primes give 'HEIGHT' with axis None. Replacing any entry by fits that disagree between primes makes the verdict 'INCONCLUSIVE'.
Routines
| Command | What it does |
|---|---|
python3 tools/thiele_gate.py IN.json [-o REPORT.json] | Command-line form of gate_family: prints a summary, writes the report, exits with status 1 on any failure |
python3 -m ratfit.degree_alias --selftest | Replays the two reference cases and two inputs that must come back INCONCLUSIVE |
IN.json is {"banked": [[x, [y, ...]], ...], "new": [...], "max_fit": 140} (optional "labels", "probe", "workers") with numbers as fraction strings; banked holds the trusted samples.
The fitting core and the grid design are loaded with import ratfit.
| Function | What it returns |
|---|---|
thiele_loo(xs, ys) | (P, Q, ok, deg) from the blind fit; thiele_loo_screened adds a modular pre-test before each exact fit |
ratrecon_with_denom(xs, ys, Qknown) | (Pnum, Qden, ok, deg): the numerator over a supplied denominator, tested on the kept-out samples, common factors divided out |
screen_modp(xs, ys, Q) | The modular version of that test; never rejects a correct Q; follow a True with ratrecon_with_denom |
degree_budget(qex, n) | Per row, for n samples: blind degree ceiling, highest denominator degree worth screening, projected denominator degrees for the next orders |
parametric_rec_interp(rec_at_point, param_grid, normalize_key) | Each recurrence coefficient as an exact polynomial in the parameters; mpoly_eval evaluates one |
coincidence_loci(PA, PB) | {Fraction: "si=sj"}: every $t\in(0,1)$ on the straight path from PA to PB where two variables are equal |
design_grid(PA, PB, n_points) | n_points fresh rational $t$ values that avoid the loci, the poles in poles and the points in exclude |
ratrecon_with_denom also returns ok False when Qknown vanishes at any sample point, because that sample would otherwise drop out of the fit unnoticed. qex maps each matrix entry $(i,j)$ and $\varepsilon$-order to a validated denominator's coefficients, and results are keyed by matrix row $i$.
parametric_rec_interp needs a complete tensor-product grid with at most deg_bound + 1 nodes per axis (deg_bound is 12 by default) and a normalize_key coefficient that is nonzero at every grid point. Its result must agree exactly at two parameter tuples off the grid. Otherwise it raises ValueError. coincidence_loci raises ValueError if two variables agree along the whole path, and design_grid if it cannot supply all the points.
The ratfit.thiele_gate submodule checks new samples against a reconstructed family.
| Function | What it returns |
|---|---|
fit(xs, ys) | A ThieleCF from an early-stopping fit that reproduces every sample left out of it, or None |
gate(cf, new_pairs) | {'ok': n, 'fail': m, 'fails': [...]} for the untrusted samples |
gate_family(banked, new) | A report for vector-valued samples [(x, [y_0, ..., y_m]), ...], one fit per component |
A ThieleCF is evaluated with cf(x) and raises CFDead at a true pole.
The ratfit.degree_alias submodule decides between primes and grid for a stalled modular reconstruction.
| Function | What it returns |
|---|---|
classify(grid, cells) | {'verdict', 'axis', 'counts'} for a list of entries, with axis equal to 'd', 'eta' or None |
classify_cell(grid, fits) | The verdict for one failing entry |
grid is the number of points per axis, $(n_d, n_\eta)$, and fits the per-prime list of ((num_d, num_e), (den_d, den_e)) fitted degrees. The rules are:
- ALIAS, with the axis to extend: every entry has a numerator at the ceiling ($n_d-1$ or $n_\eta-1$) over a trivial denominator, identically at every prime.
- HEIGHT, the combined modulus is too small and one more prime is the fix: the degrees sit below the ceiling with a nontrivial denominator (one such entry among pinned ones is enough).
- INCONCLUSIVE: the degrees differ between primes, or a numerator at the ceiling sits over a nontrivial denominator. Then you probe more entries or primes rather than choose.
The ratfit.li2close submodule gives the closed forms for logarithmic integrals.
| Function | What it returns |
|---|---|
Atom(c, W0, W1, P0, P1, lo, hi, tag) | One term $c\ln\lvert P_0+P_1t\rvert/(W_0+W_1t)$ on $(lo, hi)$ |
close_atoms(atoms, param, domain) | A Closure (.finite, .ledger, .pieces) after the divergence-cancellation check; raises DivergenceError if the check fails |
emit_mpmath(expr, name, param) | Standalone mpmath source defining name(dps=50) or name(param, dps=50); emitted_function(src, name) executes it |
RLi2 | The sympy function $\mathrm{Re}\,\mathrm{Li}_2(x)$ used in the results |
tools/thiele_gate.py, tools/li2close.py and tools/pathgrid.py forward to the package, so import thiele_gate, import li2close and from pathgrid import design_grid work too. degree_alias has no such file, but import degree_alias works with tools/ratfit/ itself on the path.
The optional arguments and the remaining functions (thiele, newton_interp, extract_stairs, row_lcm, validate, discriminator, ilin_atoms) are described in the docstrings of the four modules. The helpers fq, qpoly, poly_lcm and exact_div and the list SCREEN_PRIMES are in __all__ in tools/ratfit/__init__.py.
Used on this site
- Non-planar hexa-box: reconstruction of the path connection as exact rational functions from numerical samples.
Requirements
- Runs on: Python 3 with
python-flintfor the fitting core. - Install: put the repository's
tools/directory onPYTHONPATH, as in the self-test command. - Self-test: from the repository root,
PYTHONPATH=<repo>/tools python3 -m pytest tools/ratfit/tests -qneedspytest; 53 tests pass and 2 are skipped. The two skipped tests compare against reference data not included in the public repository. They run whenRATFIT_THIELE_REF_DIRandRATFIT_KCLOSE_DIRpoint to that data. - Triage alone:
python3 tools/ratfit/degree_alias.py --selftestneeds only the standard library and prints a line beginningdegree_alias selftest PASS. The formpython3 -m ratfit.degree_alias --selftest(withtools/onPYTHONPATH) loads the package and so needspython-flint. - Optional:
sympyandmpmath, forli2close.
Source and references
The code is tools/ratfit/ in the BootLoops repository. Thiele interpolation is classical. Ratfit applies it in exact rational arithmetic to a fixed set of samples. FiniteFlow and FireFly are two public programs that apply it modulo primes.
| Reference | What it supplies |
|---|---|
| T. Peraro, arXiv:1608.01902; code: FiniteFlow, arXiv:1905.08019 | Thiele interpolation of a rational function of one variable from sample points, with a stopping test on new points |
| J. Klappert and F. Lange, arXiv:1904.00009; J. Klappert, S. Y. Klein and F. Lange, arXiv:2004.01463; code: FireFly | The same interpolation in FireFly; screening modulo a prime before an exact reconstruction follows FireFly's approach |
| python-flint (F. Johansson, O. Benjamin and contributors); mpmath (F. Johansson and the mpmath contributors); SymPy (its development team) | The exact polynomials (fmpq_poly) of the fitting core; the numerical and symbolic parts of li2close |