Source-linked AI summary
Reconstructing Rational Functions with $\texttt{FireFly}$
Jonas Klappert, Fabian Lange
TL;DR
FireFly reconstructs multivariate rational functions over finite fields using interpolation and rational-reconstruction algorithms, and applies them to integration-by-parts reductions. Compared with Kira’s algebraic approach, reconstruction can be faster and use much less memory for huge systems with large intermediate expressions, while Kira is usually faster for smaller problems.
Problem
Multivariate rational-function reconstruction and higher-order perturbative calculations require methods that avoid manually derived recursion relations and large algebraic intermediate expressions.
Method
FireFly combines the Cuyt–Lee rational-function reconstruction algorithm with Zippel polynomial interpolation, with modifications reducing black-box probes and avoiding cancellations.
Results
For huge IBP systems with large intermediate expressions, FireFly reconstruction can be faster than Kira and requires much less memory, while Kira is usually faster for smaller problems.
Takeaways & Limitations
FireFly can selectively reconstruct requested coefficients, avoid computing large intermediate expressions, and distribute reconstruction across subsets of coefficients or sessions.
Takeaways & Limitations
The standard interpolation algorithm has complexity exponential in the number of variables and can be inefficient for sparse polynomials; Zippel interpolation also has a small probability of returning a wrong polynomial.
Abstract
from arXiv · showhide
We present the open-source $\texttt{C++}$ library $\texttt{FireFly}$ for the reconstruction of multivariate rational functions over finite fields. We discuss the involved algorithms and their implementation. As an application, we use $\texttt{FireFly}$ in the context of integration-by-parts reductions and compare runtime and memory consumption to a fully algebraic approach with the program $\texttt{Kira}$.
1 Introduction
The paper situates FireFly within multivariate finite-field interpolation and IBP reduction, addressing computational costs that make conventional multi-loop approaches difficult at scale.
- Background: Multivariate polynomial interpolation generalizes classical black-box methods but becomes costly as the number of variables grows.The paper reviews interpolation methods developed specifically for multivariate polynomials over several decades.
- Background: Multivariate rational-function interpolation has developed through several algorithmic approaches, including separate numerator–denominator evaluation, dense systems, and modified Euclidean methods.The reviewed methods differ in how they bound degrees, exploit sparsity, or solve for coefficients.
- Finite-field methods: Finite-field arithmetic supports exact interpolation while avoiding coefficient number swell, and FireFly combines Cuyt–Lee rational reconstruction with Zippel polynomial interpolation.The implementation also modifies these methods to reduce black-box probes.
- IBP reductions: IBP relations reduce Feynman integrals either through recursively derived relations or by solving large systems formed from assigned propagator powers.Recursive reductions reach master integrals but are difficult to derive at higher orders, while Laporta systems can be expensive in memory and runtime.
- IBP reductions: Finite-field techniques have been proposed to reduce Laporta-system size and improve runtime, motivating FireFly’s interpolation-based comparison with Kira.The paper compares the approaches and discusses the advantages and disadvantages of the finite-fields-interpolation approach.
- Related work: FireFly’s scope is distinct from generalized-unitarity applications, which had already interpolated functions with up to four variables but are not pursued here.The paper explicitly limits its discussion of that related application area.
2 Functional interpolation over finite fields
The section develops black-box interpolation over finite fields, from univariate Newton interpolation to sparse multivariate Zippel and rational-function reconstruction. It emphasizes probe efficiency, probabilistic termination, and FireFly’s adoption of a sparse rational-function algorithm.
- Foundations: Black-box interpolation reconstructs a function from evaluations over a field, with finite fields providing exact arithmetic without number swell.The interpolated coefficients remain elements of the finite field.
- Univariate interpolation: Newton interpolation supports unknown degrees because adding a new term leaves previously computed terms unchanged.An early-termination test stops after a chosen number of vanishing coefficients, with a quantified success probability.
- Multivariate interpolation: Recursive multivariate Newton interpolation requires Q_i(D_i + 2) probes and grows exponentially with the number of variables, making it inefficient for sparse polynomials.The method repeatedly treats one variable as univariate while promoting coefficients to polynomials in the remaining variables.
- Multivariate interpolation: Zippel interpolation exploits sparsity by interpolating one variable at a time and probabilistically pruning coefficients that vanish at an anchor point.Careful random anchor-point selection is required because the vanishing assumption can fail.
- Multivariate interpolation: 26 probes with improved Zippel interpolation versus 41 with the original version and 245 with recursive Newton interpolation.The example uses temporary pruning to reduce the improved Zippel probe count.
- Rational-function interpolation: FireFly adopts the Cuyt–Lee rational-function algorithm combined with Zippel polynomial interpolation because it needs only the variable count and uses rational-function sparsity.Its adjusted reconstruction parameter yields roughly 1% false-positive results, while solving one dense coefficient system can require O(T^3) operations.
3 FireFly
FireFly is an open-source C++ library for reconstructing multivariate rational functions and polynomials over finite fields, with parallel interpolation and configurable arithmetic. Its benchmarks show that variable ordering and sparse-shift scans can substantially reduce probes and runtime, especially for sparse functions, while dense functions benefit less.
- Library and interface: FireFly implements functional interpolation and rational-number reconstruction algorithms in a publicly available C++ library.The library supports reconstruction over finite fields and promotion of coefficients to the rational field Q.
- Arithmetic and build: Finite-field arithmetic is the default computational setting, with optional FLINT or custom arithmetic implementations and GMP support for Chinese-remainder reconstruction.FireFly represents finite-field integers with FFInt and can use multiple prime fields when one field is insufficient.
- Library and interface: The Reconstructor interface supports multivariate reconstruction, parallel interpolation through a thread pool, sparse-shift scans, and retrieval of RationalFunction results.Its constructor specifies the number of variables and threads, while reconstruction and result access are exposed as member functions.
- Benchmarks: ∼90000 black-box probes for f1 fall to ∼20000 with optimal ordering and sparse-shift scanning, reducing runtime from 3.6 s to 1.7 s.The shift scan itself requests 184 evaluations; storing all permuted shifts for 20 variables uses ∼120 MiB, compared with ∼7 MiB for reconstruction.
- Benchmarks: Dense functions f2 and f3 receive smaller optimization benefits because parameter reordering is unhelpful; sparse-shift scans provide slightly faster runtime, and probe counts for f3 scale linearly relative to f2.The f2 probe counts include 204 evaluations for finding a shift and 102358 for full functional interpolation in the first prime field.
- Benchmarks: For f4, optimal variable ordering reduces probes to approximately one third and runtime to almost one fifth, while combining ordering with a sparse shift reaches 2.8 s.The combined optimization requires less than a quarter of the black-box probes used without optimizations.
4 Application to IBP reductions
FireFly applies finite-field rational-function reconstruction to IBP reductions, where linear relations reduce Feynman integrals to master integrals. Across examples, it often reduces memory and equation counts, while runtime depends strongly on topology, parameter complexity, and parallelism.
- IBP reductions: IBP relations are linear relations among scalar Feynman integrals that can be recursively combined to express all integrals through master integrals.Integral difficulty can be ordered using the sums of positive and negative propagator powers, r and s.
- topo7 examples: For topo7 without masses, reconstruction is four times faster at smax = 2, but Kira becomes slightly faster at smax = 4 with eight threads.Reconstruction selects 730, 1837, and 3970 mandatory equations for smax = 2, 3, 4, versus Kira’s 2774, 7994, and 17548 equations.
- topo7 examples: For the massive topo7 configuration, reconstruction is slower by a factor of 3.4 at smax = 2 and 3.0 at smax = 4, while both approaches experience runtime increases of up to two orders of magnitude.The reconstruction selects fewer mandatory equations, but coefficient complexity and black-box probes increase substantially with smax.
- parallel scaling: Increasing threads benefits reconstruction more than Kira: the gap falls from almost four times longer at 10 threads to 40% at 80 threads.Kira’s memory consumption increases drastically with additional Fermat instances, whereas reconstruction could profit from still more threads.
- topo5 examples: For topo5, both approaches have similar runtimes, but reconstruction requires significantly less memory and uses finite-field probes to solve the systems.For smax = 1, 2, 3, reconstruction uses one, two, and three prime fields, respectively, with forward elimination consuming about 83% of probe time.
- topo5 examples: For the highly complicated topo5 m case, reconstruction is four times faster and uses one to two orders less memory than the algebraic approach.It selects 1785 mandatory equations versus Kira’s 3140 and requires about 1.5 · 10^6 black-box probes over two prime fields.
5 Conclusions
FireFly reconstructs multivariate rational functions and can support IBP reductions competitively, especially when algebraic methods face huge intermediate expressions and memory demands.
- FireFly is an open-source C++ library for reconstructing polynomials and multivariate rational functions, with modifications reducing black-box probes and cancellations.
- In IBP reductions linked to Kira, reconstruction can become faster and use much less memory when systems are huge and intermediate expressions are large.
- The reconstruction approach avoids large intermediate expressions and selects only requested coefficients, unlike the algebraic approach.
- Reductions can be distributed across computers or sessions, while FireFly can reconstruct coefficient subsets or individual coefficients.
- FireFly’s implementation remains strongly limited by pyRed numerical solutions, which consume most CPU time in the examples.
- FireFly can also participate in hybrid approaches, including replacing algebraic multiplication with multivariate Newton interpolation over Z.
Maximal Quotient Rational Reconstruction
Maximal Quotient Rational Reconstruction uses Euclidean-algorithm quotients to identify rational candidates from modular data, with a tolerance parameter controlling acceptance and error probability.
- The uniqueness proof for rational reconstruction requires m ≥ 2|n||d|, although separate bounds could be adjusted if the unknown number were known beforehand.
- Monagan’s MQRR selects the rational number associated with the largest quotient encountered during the Euclidean algorithm.
- MQRR returns a rational number n / d congruent to e modulo m when T * |n| * d < m, or FAIL otherwise.
- MQRR’s parameter T sets a quotient lower bound, and the algorithm fails when encountered quotients are smaller.
- FireFly chooses c = 10 in T = 2^c⌈log2 m⌉, roughly corresponding to 1% false-positive reconstructions.
Solving shifted transposed Vandermonde systems
Shifted transposed Vandermonde systems are solved through interpolation-style basis polynomials whose coefficients provide the inverse transformation in quadratic time.
- The presented solution strategy specifically targets the shift with one power, while general shifts require a separate strategy.
- Shifted Vandermonde matrices differ from usual systems by using powers beginning at one rather than zero, and their solution is closely related to Lagrange interpolation.
- The basis polynomial Bj(z) vanishes at every evaluation point except vj, where it equals one.
- The coefficients A_jk form the inverse of the shifted Vandermonde matrix, so multiplying by them solves the system.
- A master polynomial can generate each Bj through divisions by z − vj, yielding total complexity O(M^2).
B Parallelization of FireFly
FireFly’s parallel reconstruction separates probe feeding from interpolation and solves shifted Vandermonde systems from probe values and contributing degrees.
- Each PolyReconst and RatReconst object uses mutexes to protect status and static data during parallel execution.
- Interpolation uses a two-step paradigm: black-box probes are fed and queued first, then interpolation and reconstruction proceed independently.
- The shifted Vandermonde solver takes polynomial probes, corresponding inserted values, and contributing degrees, returning coefficients for those degrees.
- The solver computes shifted evaluation values by multiplying inserted values raised to their contributing degrees.
- The algorithm constructs auxiliary arrays and performs coefficient calculations before returning the solved coefficients.