Tropical Sampler
Tropical Sampler is a Monte Carlo integrator for integrals, over positive variables, of products of polynomials with positive coefficients raised to powers. It takes the monomial exponent vectors and the powers and returns an unbiased estimate with a statistical error bar, and the exact rational value of the simplified ("tropical") integral it samples from. It is a Python implementation by BootLoops of the tropical sampling algorithm of Michael Borinsky, Anna-Laura Sattelberger, Bernd Sturmfels and Simon Telen (Algorithm 1 of arXiv:2204.06414), whose own Julia program is on MathRepo.
What it does
The integrals have the form
$$ Z \;=\; C\int_{\mathbb{R}_+^E} \prod_k Q_k(t)^{u_k}\,\prod_{e=1}^{E}(1+t_e)^{-c}\,dt , $$
where every $Q_k$ has positive coefficients (no cancellation between terms, or "subtraction-free"), the $u_k$ are real powers, and $c$ is large enough for convergence. Such integrals appear as marginal likelihoods in Bayesian statistics, as generalized hypergeometric integrals, and as Feynman and string integrals in parametric form.
In logarithmic variables $y=\log t$, replacing each polynomial by its largest monomial makes the log of the integrand piecewise linear. This is the tropical approximation. The linear pieces live on cones fixed by the Newton polytopesthe Newton polytope of a polynomial is the convex hull of the exponent vectors of its monomials of the $Q_k$. Together the cones form the normal fanthe division of direction space into cones according to which vertex of a polytope is the extreme one in that direction of the polytopes' Minkowski sum (the set of all sums of one point from each polytope), with a unit segment per variable added for the decay factors.
On a cone spanned by integer rays $r_i$, the columns of a matrix $R$, the approximate integral is elementary, $c_\sigma=|\det R|/\prod_i\beta_i$, with $\beta_i\gt0$ the decay rate along $r_i$. The sampler works in three steps.
- Fan.
build_fanconstructs the cones in exact integer arithmetic and returns each $c_\sigma$ and their sum $I^{\mathrm{tr}}$ asFractions. Two checks come with it. Random directions must each fall in exactly one cone, and a refinement of the fan must leave $I^{\mathrm{tr}}$ unchanged. - Sample. A cone is drawn with probability $c_\sigma/I^{\mathrm{tr}}$, and a point in it as $y=R\lambda$ with each $\lambda_i$ exponential of rate $\beta_i$.
- Weight. The point is weighted by the ratio of the true integrand to the tropical one. Positive coefficients keep that ratio bounded, so $\hat Z=C\,I^{\mathrm{tr}}\,\overline{w}$ is unbiased with the usual $1/\sqrt{n}$ error.
Two variants cut the variance and stay unbiased. The stratified one allocates samples per cone from a pilot run (Neyman allocation). The tilted one also fits the slope of the log-weight along each ray and lowers the exponential rates to match (never raises them, so the weights stay bounded). When the powers are large, as when they count data, only the tilted variant converges usefully.
The pilot-based allocation and the tilting are BootLoops additions to Algorithm 1. The authors' program already allocates samples cone by cone, in proportion to the cone integrals.
The sampler has these limits:
build_fanaccepts any integer point sets and weights, but the weight function in the file is written for one family. In it each $Q_k$ is a sum, over subsets $D$ of the variables, of products $\prod_{e\in D}(1+4t_e)$ with positive integer multiplicities, with $c=N+2$ and $C=4^{-(E+1)N}$. This is the form in which marginal likelihoods of phylogenetic trees arise. Another family needs its ownlog_weight.- Expect three to four significant digits for fans of a few thousand cones in seven variables. That is enough for a numerical cross-check or for ranking competing integrals, with further digits left to an exact method.
- Polynomials with coefficients of both signs are out of scope, because the weight bound fails.
The cegm_gj scripts. A companion set of scripts sits in the same package directory, under cegm_gj/. It uses the same cone decomposition, with deterministic high-precision quadrature in place of sampling, for the Grassmannian string integral on $X(3,6)$ (the space of six points in the plane) of Arkani-Hamed, He and Lam (arXiv:1912.08707). Splitting an integral over the cones of the normal fan and mapping each cone to the unit cube is the sector decomposition of the paper of Borinsky, Sattelberger, Sturmfels and Telen.
The integrand has four positive variables and twenty $3\times3$ minors raised to kinematic powers, in the positive coordinates of Giménez Umbert and Sturmfels (arXiv:2501.10805). Log space splits into 48 maximal cones, refined to 52 simplicial ones.
Mapped to the unit cube, each cone's integrand is smooth, so tensor-product Gauss–Jacobi quadrature in arbitrary precision converges geometrically in the nodes per axis $n$, which quadrature over the undivided domain does not. A value counts as correct to $D$ digits only when two runs at different $n$ and working precision agree to $D$ digits, rounded down. Kinematic points, fan and certificates are specific to $X(3,6)$.
On its 52-cone decomposition cegm_gj computed the $X(3,6)$ integral to 60 digits at one kinematic point and 32 at a second. The sampler gave Monte Carlo values of five-taxon (five-species) marginal-likelihood integrals, checked against exactly known ones. The integrals themselves are described on the Grassmannian string integral and Phylogenetics pages.
Examples
Build a fan and check it. The fan has two variables and one polynomial with power 2 whose Newton polytope is the unit square. The decay $c=7$ per variable is entered as a segment from the origin to each unit vector with weight $-7$. With NumPy and SciPy installed (see Requirements), run this from the package directory tools/tropical-sampler/:
import numpy as np from fractions import Fraction from tropical_sampler import build_fan, tiling_probe E = 2 pat = np.array([[0, 0], [1, 0], [0, 1], [1, 1]], dtype=np.int64) seg1 = np.array([[0, 0], [1, 0]], dtype=np.int64) seg2 = np.array([[0, 0], [0, 1]], dtype=np.int64) groups = [(2, pat), (-7, seg1), (-7, seg2)] rng = np.random.default_rng(0) fan = build_fan(groups, E, rng) ok, cmin, cmax = tiling_probe(fan, rng, nprobe=500) extra = np.array([[0, 0], [2, 1], [1, 2]], dtype=np.int64) fan2 = build_fan(groups, E, rng, refine_extra=extra)
fan['cones'] holds 4 cones, the four quadrants, each a dict with the ray matrix R, gradient g, rates beta and exact csigma ($1$, $\tfrac14$, $\tfrac14$, $\tfrac1{16}$). fan['Itr'] is Fraction(25, 16), and tiling_probe returns (True, 1, 1): each of 500 random directions lies in exactly one cone. With the triangle extra added at weight zero, fan2 has 7 cones and the same Fraction(25, 16).
Estimate the integral. On the same fan the polynomial is $Q(t)=\sum_{D\subseteq\{1,2\}}\prod_{e\in D}(1+4t_e)=(2+4t_1)(2+4t_2)$ with $u=2$, and $N=5$ so that $c=7$ matches the segment weights:
from tropical_sampler import make_eval_data, estimate_logZ, estimate_logZ_tilt
N, u = 5, 2
Dsets = [frozenset(), frozenset({0}), frozenset({1}), frozenset({0, 1})]
evdata = make_eval_data([(u, Dsets)], E)
logZ, se_rel, mean_w, se_w, wmin, wmax = estimate_logZ(
fan, evdata, N, E, 200_000, rng, 0.0)
logZ_t, se_rel_t, Zint, n_used, wmin_t, wmax_t = estimate_logZ_tilt(
fan, evdata, N, E, 20_000, 200_000, rng, 0.0)
The last argument is $\log C$, and 0.0 returns the bare integral. estimate_logZ draws 200,000 points, and its relative standard error here is a few parts in a thousand. estimate_logZ_tilt takes a pilot size and a main size. This small integral factorizes into two Beta-function integrals and equals $(22/15)^2\approx2.151$, so exp(logZ) should sit within a few error bars of it.
Routines
tropical_sampler.py has one command-line mode, the self-test. The other commands are scripts under cegm_gj/.
| Command | What it does |
|---|---|
tropical_sampler.py --selftest | Builds the two-variable fan of the first example and runs its checks |
t3_prod.py sanity [--procs P] [--engine E] | Evaluates the integral at the first built-in kinematic point over all 52 cones and compares with the stored reference value |
t3_prod.py cert --point {1,2} | Writes point{N}_certificate.json: kinematics, exact momentum conservation, convergence conditions, minimum decay rate over the 52 cones, fan checksum |
t3_prod.py run --point {1,2} --n N --prec BITS [--procs P] [--cpp C] [--engine E] | Re-derives the certificate, computes one high-precision value and writes it with its settings to run_p{point}_n{N}_b{BITS}.json |
gates.py A B [--bar D] [--relmax R] | Counts the agreeing digits of two run JSONs or decimal strings, rounded down; exits 0 at D or more (default 30) |
bank.py | Reassembles the recorded $X(3,6)$ values from the run JSONs in the directory named in the environment variable CEGM_GJ_RUNDIR, recomputing every two-run comparison |
tropical_cones.py | Builds the 48-cone, 52-subcone fan with its coverage check and writes fan_x36.json to the current directory |
Notes on the cegm_gj commands:
- Options.
--enginetakesplain,hoist(a reordered loop) orc(a C inner loop), and the three are interchangeable. Withhoistorcthe name of the run file gains the suffix_hoistor_c.--cppsets how finely each cone is split across processes. With--relmax,gates.pyalso requires a relative difference belowR. - Output. Logs and records go to the directory named in the environment variable
CEGM_GJ_OUT, or the current directory when unset. Value strings end in a decimal exponent such ase3, so read them whole. - Cautions. Never run
tropical_cones.pyinside the package directory, where it would overwrite the stored fan.bank.pystops with an error if a comparison falls short. It works only on the recorded set of $X(3,6)$ runs.
The functions are imported from tropical_sampler.py.
| Function | What it returns |
|---|---|
build_fan(groups, E, rng) | The exact normal fan as dict(cones, Itr, E); refine_extra adds a weight-zero polytope |
tiling_probe(fan, rng, nprobe) | (ok, min_cover, max_cover) from the check that random directions each lie in exactly one cone |
make_eval_data(patterns, E) | The arrays that log_weight uses |
log_weight(Y, evdata, N, E) | Log of true integrand over tropical integrand at a block of points in log coordinates, one per row |
sample_tropical(fan, nsamples, rng) | A generator of blocks of points drawn from the tropical density |
estimate_logZ(fan, evdata, N, E, nsamples, rng, ln_prefac) | Plain estimator: (logZ, relative_stderr, mean_w, se_w, wmin, wmax) |
estimate_logZ_strat(fan, evdata, N, E, n_pilot, n_main, rng, ln_prefac) | Stratified by cone with pilot-based allocation: (logZ, relative_stderr, Z_int, n_used, wmin, wmax) |
estimate_logZ_tilt(fan, evdata, N, E, n_pilot, n_main, rng, ln_prefac) | Stratified with tilting, same tuple; the variant for large powers |
groups is a list of (weight, integer point set) pairs: a polynomial with weight $u_k$, or a variable's segment with weight $-c$. patterns is a list of (u_k, Dsets), with Dsets a list of frozensets of variable indices, where repeats count as multiplicity.
The lower-level routines (idet, primitive_normal, hull_vertices, minkowski_vertices, ln_fraction) are defined in tropical_sampler.py. GUIDE.md in the package lists the modules of cegm_gj/.
Requirements
- Runs on: Python 3 with NumPy and SciPy for the sampler (
scipy.spatial.ConvexHull, which calls Qhull).cegm_gjalso needsgmpy2,mpmathandsympy. - Install: nothing to build. Install SciPy with
pip install scipy. - Self-test:
python3 tropical_sampler.py --selftestprints one summary line that ends inPASS. It exits with the number of failed checks, 0 on a pass, and takes about a second. - Self-test of
cegm_gj:python3 cegm_gj/t3_prod.py sanity --procs 4prints a one-line JSON verdict and exits 0 on a pass. Run it withCEGM_GJ_OUTset to a scratch directory, so that its log file goes there and not to the current directory. The--procsdefault is 16, so set it on a small machine. - Optional: the C engine behind
--engine ciscchunk.c. It needs the MPFR and GMP headers. Build it in place withgcc -O2 -shared -fPIC -o cchunk.so cchunk.c -lmpfr -lgmp.
Source and references
The code is tools/tropical-sampler/ in the BootLoops repository.
| Reference | What it supplies |
|---|---|
| M. Borinsky, A.-L. Sattelberger, B. Sturmfels and S. Telen, "Bayesian integrals on toric varieties", arXiv:2204.06414; code: BayesianIntegrals | The sampling algorithm (Algorithm 1) and the sector decomposition over the cones of the normal fan |
| M. Borinsky, arXiv:2008.12310 | The tropical Monte Carlo method on which the sampling algorithm is built |
| N. Arkani-Hamed, S. He and T. Lam, "Stringy canonical forms", arXiv:1912.08707 | The Grassmannian string integral and its convergence conditions |
| B. Giménez Umbert and B. Sturmfels, "Splitting CEGM amplitudes", arXiv:2501.10805 | The positive coordinates and the split-kinematics reference value |