zippel

A bunch libraries to support doing Feynman integral reduction by sparse interpolation over finite fields in Rust.

IBP systems are eliminated numerically modulo word-sized primes, and the exact rational coefficients are recovered from evaluations alone.

• zippel-interp: Zippel's black-box sparse polynomial interpolation over prime fields
• zippel-interp::rational: Rational function reconstruction ala the method of Thiele and Zippel
• zippel-interp::benor: Ben-Or/Tiwari interpolation from about two evaluations per term
• zippel-lift: Lifts to Q by CRT and rational number reconstruction
• zippel-laporta: IBP generation and Laporta elimination over GF(p)
• zippel-gcd: Multivariate GCD, cofactors and LCM of polycore polynomials
• zippel-gcd::pgcd: Zippel's modular GCD with LINZIP interpolation
• zippel-gcd::huang_gao: Huang–Gao GCD by separated Hensel lifting
• zippel-gcd::huang_monagan: Huang–Monagan GCD by prime substitution
• zippel-gcd::hu_monagan: Hu–Monagan GCD and cofactor interpolation
• zippel-gcd::hu_monagan_bivariate: Hu–Monagan GCD with bivariate images

cargo build
cargo test

cargo run -p zippel-interp --example determinant
cargo run -p zippel-interp --example linsolve
cargo run -p zippel-laporta --example hello
cargo run -p zippel-laporta --example bubble
cargo run --release -p zippel-laporta --example box
cargo run --release -p zippel-laporta --example double_box
cargo run -p zippel-gcd --example demo

Example

The massless one-loop bubble with dots, reduced to its master integral $I(1,1)$, where

$$ I(a_1, a_2) = \int \frac{d^{d k}{(k}2)^{{a_1} ((k + q)2){a_2}}, \qquad q}2 = s. $$

use zippel_laporta::ibp::Family;

let bubble = Family {
    vars: vec!["d", "s"],
    loops: 1,
    props: vec![(vec![1, 0], vec![]), (vec![1, 1], vec![])], // k^2, (k + q)^2
    lines: 2,
    legs: vec![vec![vec![0, 0, 2]]], // 2 q.q = 2s
    symmetries: vec![vec![1, 0]],
};
let (system, plan, coefficients) = bubble.reduce(&[vec![2, 1], vec![2, 2]], 2, 0).unwrap();
print!("{}", system.render(&plan, &coefficients));

I(2,1) = (-d + 3) / (s) * I(1,1)
I(2,2) = (d^2 - 9*d + 18) / (s^2) * I(1,1)

References

• J. Hu, M. Monagan, A fast parallel sparse polynomial GCD algorithm, J. Symbolic Comput. 105 (2021).
• M. Monagan, Speeding up polynomial GCD, a crucial operation in Maple, Maple Transactions (2022).
• Q.-L. Huang, M. Monagan, A New Sparse Algorithm for Polynomial GCD over Integers, arXiv:2609.10626v1, 2026.
• Q.-L. Huang, X.-S. Gao, Sparse Polynomial GCD Algorithms Asymptotically Linear in All Fundamental Parameters, arXiv:2609.08074v1, 2026.
• R. Zippel, Probabilistic algorithms for sparse polynomials, EUROSAM 1979.
• R. Zippel, Interpolating polynomials from their values, J. Symbolic Comput. 9 (1990).
• J. de Kleine, M. Monagan, A. Wittkopf, Algorithms for the non-monic case of the sparse modular GCD algorithm, ISSAC 2005.
• M. Ben-Or, P. Tiwari, A deterministic algorithm for sparse multivariate polynomial interpolation, STOC 1988.
• E. Kaltofen, W. Lee, Early termination in sparse interpolation algorithms, J. Symbolic Comput. 36 (2003).
• P. S. Wang, M. J. T. Guy, J. H. Davenport, P-adic reconstruction of rational numbers, SIGSAM Bull. 16 (1982).
• K. G. Chetyrkin, F. V. Tkachov, Integration by parts: The algorithm to calculate beta-functions in 4 loops, Nucl. Phys. B 192 (1981).
• S. Laporta, High-precision calculation of multi-loop Feynman integrals by difference equations, Int. J. Mod. Phys. A 15 (2000), arXiv:hep-ph/0102033.
• J. Klappert, F. Lange, Reconstructing rational functions with FireFly, Comput. Phys. Commun. 247 (2020), arXiv:1904.00009.
• J. Klappert, F. Lange, P. Maierhöfer, J. Usovitsch, Integral reduction with Kira 2.0 and finite field methods, Comput. Phys. Commun. 266 (2021), arXiv:2008.06494.
• X. Guan, X. Liu, Y.-Q. Ma, W.-H. Wu, Blade: A package for block-triangular form improved Feynman integrals decomposition, arXiv:2405.14621.
• F. Lange, J. Usovitsch, Z. Wu, Kira 3: integral reduction with efficient seeding and optimized equation selection, arXiv:2505.20197.

License

Released under the MIT License. See the LICENSE file for details.