PaperlayerView exact revision on arXiv

Source-linked AI summary

FiniteFlow: multivariate functional reconstruction using finite fields and dataflow graphs

Tiziano Peraro

arXiv:1905.08019v2hep-phcs.SChep-th

TL;DR

Complex algebraic calculations require precise methods for increasingly complex scattering predictions. FiniteFlow combines finite-field algorithms, dataflow graphs, and functional reconstruction, enabling applications beyond traditional computer algebra with reasonable resources.

  • Problem

    Higher-loop, multi-particle, and multi-scale scattering predictions require increasingly complex algebraic calculations for precise theoretical results.

  • Method

    FiniteFlow combines low-level finite-field algorithms, dataflow graphs for complex calculations, and multivariate functional reconstruction of analytic results.

  • Results

    The framework supports multi-loop scattering-amplitude applications and has been successfully applied to state-of-the-art problems beyond traditional computer algebra using reasonable computing resources.

  • Takeaways & Limitations

    FiniteFlow sidesteps large intermediate expressions, supports high-level implementation and automated parallelization, and handles diverse algebraic problems.

  • Takeaways & Limitations

    The released implementation is proof-of-concept, and MPI-based parallelization across unrelated machines is not supported by the discussed approach.

Abstract

from arXiv · show

Complex algebraic calculations can be performed by reconstructing analytic results from numerical evaluations over finite fields. We describe FiniteFlow, a framework for defining and executing numerical algorithms over finite fields and reconstructing multivariate rational functions. The framework employs computational graphs, known as dataflow graphs, to combine basic building blocks into complex algorithms. This allows to easily implement a wide range of methods over finite fields in high-level languages and computer algebra systems, without being concerned with the low-level details of the numerical implementation. This approach sidesteps the appearance of large intermediate expressions and can be massively parallelized. We present applications to the calculation of multi-loop scattering amplitudes, including the reduction via integration-by-parts identities to master integrals or special functions, the computation of differential equations for Feynman integrals, multi-loop integrand reduction, the decomposition of amplitudes into form factors, and the derivation of integrable symbols from a known alphabet. We also release a proof-of-concept C++ implementation of this framework, with a high-level interface in Mathematica.

1 Introduction

FiniteFlow addresses the difficulty of obtaining analytic high-energy-physics predictions when intermediate expressions become prohibitively large. It combines finite-field algorithms, dataflow graphs, and functional reconstruction so complex calculations can be implemented and evaluated efficiently.

  • Large intermediate expressions can be orders of magnitude more complicated than final results, with cancellations often occurring only near the end of analytic calculations.
  • Finite-field evaluations provide fast, exact numerical operations while avoiding multi-precision arithmetic and enabling analytic expressions to be reconstructed afterward.
  • FiniteFlow combines low-level finite-field algorithms with dataflow graphs whose nodes represent basic algorithms and whose connections define more complex calculations.
  • The framework supports high-level-language and computer-algebra-system interfaces without requiring users to implement low-level numerical details.
  • Dataflow graphs can be evaluated repeatedly and in parallel across cores, nodes, or machines using an algorithm-independent strategy.
  • FiniteFlow applies a novel use of dataflow graphs to rational numerical algorithms over finite fields combined with functional reconstruction, including high-energy-physics problems.

2 Finite fields and functional reconstruction

The paper uses finite fields to evaluate rational functions exactly and reconstruct their analytic forms from numerical samples. Its multivariate strategy recursively reduces reconstruction to univariate problems while handling bad evaluation points and avoiding huge dense ansätze.

  • 2.1 Finite fields and rational functions: FiniteFlow uses prime-modulus fields Zp, where nonzero elements have inverses and rational operations are implemented through modular arithmetic.
  • 2.1 Finite fields and rational functions: Wang’s algorithm can reconstruct rational numbers from their images in Zp when the modulus is sufficiently large relative to numerator and denominator sizes.
  • 2.1 Finite fields and rational functions: Machine-size integer constraints require primes p < 2^64, while the Chinese remainder theorem can overcome this limitation using moduli with no common factors.
  • 2.2 Multivariate functional reconstruction: The reconstruction procedure maps finite-field coefficients to rational coefficients with Wang’s algorithm and validates them against evaluations over other finite fields.
  • 2.2 Multivariate functional reconstruction: Bad evaluation points can arise from analytic or spurious intermediate singularities and are replaced during numerical reconstruction.
  • 2.2 Multivariate functional reconstruction: Thiele’s interpolation handles general univariate rational functions, while the multivariate method combines it with polynomial reconstruction after determining total numerator and denominator degrees.
  • 2.2 Multivariate functional reconstruction: Multivariate polynomial reconstruction treats one variable as univariate and recursively reconstructs coefficient polynomials in the remaining variables.
  • 2.2 Multivariate functional reconstruction: The required evaluations are comparable to, or fewer than, a degree-based general ansatz, while avoiding the huge dense systems that make the ansatz impractical for complex functions.

3 Dataflow graphs

FiniteFlow builds numerical algorithms over finite fields from dataflow-graph nodes, then extends graph composition with learning phases and reusable subgraphs. These mechanisms support flexible organization and repeated evaluation of complex calculations.

  • Graph structure: Dataflow graphs are directed acyclic graphs whose nodes execute numerical algorithms on incoming lists and produce outgoing lists.The graph’s input node supplies variables z, while an output node returns the procedure’s resulting list.
  • Graph structure: FiniteFlow combines basic numerical algorithms as graph building blocks to represent complete calculations.Nodes can encode operations such as rational-function evaluation or linear-system solution, with outputs feeding subsequent nodes.
  • Graph execution: Nodes are evaluated in increasing depth order, storing outputs for reuse by downstream nodes.Only nodes needed to evaluate the selected output are recursively collected and ordered.
  • Learning phases: Learning phases let algorithms determine output structure numerically before their results can feed other nodes.This is needed when output length depends on properties such as a linear system’s rank or whether it is determined.
  • Subgraphs: Embedded subgraphs organize complex graphs and support repeated evaluation through simple, memoized, and mapped forms.Memoized subgraphs reuse the last output for identical inputs, while subgraph maps evaluate a graph across multiple input lists.

4 Numerical algorithms over finite fields

FiniteFlow supplies finite-field numerical building blocks for rational-function evaluation, linear solving, matrix operations, and graph-based fitting. Its algorithms emphasize efficient evaluation, learned system structure, and reduction of unnecessary computation.

  • Rational functions: Rational-function nodes evaluate lists of functions over input values, using Horner’s scheme for efficient polynomial computation.A degree-R univariate polynomial requires R multiplications and R additions in Horner form.
  • Rational functions: Rational functions are computed as polynomial ratios, but evaluations fail at inputs where denominators vanish.Such inputs produce singular points for the numerical procedure.
  • Linear solvers: Linear solvers learn dependent and independent unknowns and remove redundant equations during an initial numerical phase.This learned structure improves later evaluations and can identify unknowns that vanish after solving.
  • Linear solvers: Parametric systems are evaluated and solved over finite fields, with outputs determined by the chosen ordering and requested unknowns.The solver can return only the solution portion involving specified needed unknowns, enabling further optimization.
  • Linear solvers: For dense systems, Gauss elimination uses forward elimination followed by back substitution to obtain the solution.The implementation stores matrix rows as contiguous integer arrays and processes equations through row-echelon forms.
  • Linear fits: Subgraph fitting can find vanishing linear combinations of graph outputs and estimate or simplify their algebraic complexity.With empty z and fm = 0, the algorithm searches for numerical-coefficient relations among the outputs.

5 Reduction of scattering amplitudes

This section describes reducing scattering amplitudes to master integrals by solving sparse IBP systems numerically over finite fields and reconstructing the final rational coefficients analytically. Dataflow graphs connect amplitude coefficients, IBP solutions, and matrix multiplication while avoiding large analytic IBP tables.

  • Integration-by-parts reduction to master integrals: IBP, Lorentz invariance, symmetry, and mapping relations form a large sparse system that reduces Feynman integrals to master integrals.The solver’s ordering of unknowns affects efficiency and the equations retained after mark-and-sweep.
  • Integration-by-parts reduction to master integrals: The reduction coefficients are rational functions of kinematic invariants and the dimensional regulator ϵ.Preferred master integrals may be arbitrary combinations chosen for properties such as simpler poles, better analytic behavior, or uniform transcendental weight.
  • Integration-by-parts reduction to master integrals: A dataflow graph combines input variables, unreduced-amplitude coefficients, a numerical sparse IBP solver, and a final matrix multiplication.The IBP node learns the relevant system numerically, after which the output node can be defined; an identity-matrix branch handles masters appearing in the unreduced amplitude.
  • Integration-by-parts reduction to master integrals: Repeated graph evaluations reconstruct analytic amplitude-reduction coefficients without deriving large and complex IBP tables.Numerical IBP tables avoid computing and applying huge analytic substitution lists, and this has enabled reductions where such tables exceed reasonable resources.
  • Reduction to special functions and Laurent expansion in ϵ: A second dataflow graph can take the coefficient graph as a subgraph and compute its Laurent expansion in ϵ in terms of special functions.The first graph computes master-integral coefficients, while the second performs the expansion operation.

6 Differential equations for master integrals

This section applies the dataflow approach to reconstruct differential equations for master integrals, including systems in ϵ-form for uniform-transcendental-weight bases. The graphs perform numerical IBP reduction and matrix construction, avoiding analytically computed IBP tables.

  • Reconstructing differential equations: Differential equations for master integrals are computed by differentiating them with respect to kinematic invariants and reducing the resulting integrals through the IBP system.The resulting differential-equation matrices are obtained by matrix multiplication of derivative coefficients and IBP-reduction coefficients.
  • Reconstructing differential equations: The differential-equation dataflow graph mirrors amplitude reduction, with inputs, derivative coefficients, an IBP system, and a final matrix-multiplication node.An identity-matrix branch is added when master integrals also appear in unreduced derivatives.
  • Reconstructing differential equations: Reconstructing differential equations directly avoids computing analytic IBP tables and usually substantially simplifies the calculation.This is the differential-equation analogue of reconstructing amplitude reductions from numerical graph evaluations.
  • ϵ-form differential equations: For a uniform-transcendental-weight basis, the differential-equation matrices have ϵ dependence as a simple ϵ prefactor, defining ϵ-form or canonical systems.Such systems are typically easier to reconstruct because of their particularly simple functional structure.
  • ϵ-form differential equations: A graph evaluating matrices divided by ϵ can test ϵ-form numerically by checking that its output remains independent of ϵ at fixed kinematics.The modified graph adds a 1/ϵ node and multiplies it with the original matrix output.
  • Known alphabets: When a known alphabet is available, differential equations for uniform-transcendental master integrals can be obtained through a numerical linear fit to derivatives of logarithms of its letters.The construction uses one graph for the letter derivatives and matrix elements, then a subgraph multi-fit graph for the basis-function fit.
  • Differential equations with square roots: The discussion of uniform-transcendental integrals initially neglects cases where their definitions require square-root prefactors.Square roots can be accommodated using more general finite fields, although they are not necessary for computing differential equations in the described approach.

7 Integrand reduction

FiniteFlow performs multiloop integrand reduction by fitting coefficients of a chosen integrand basis over finite fields, using cuts to split an impractical global fit into smaller systems. The resulting dataflow graph can feed later IBP reduction and special-function decomposition, although some sectors require additional seed integrals.

  • 7 Integrand reduction: The method targets the challenging task of representing an unreduced amplitude as a linear combination of standard-form Feynman integrals.Integrand reduction is presented as an efficient approach suitable for complex processes.
  • 7 Integrand reduction: Integrand reduction rewrites amplitudes as linear combinations of basis functions, with kinematic-dependent coefficients determined by linear fits.The basis must be complete in the loop components, while coefficients are independent of loop momenta.
  • 7 Integrand reduction: A global fit is impractical because it produces a dense system as large as the number of unknown coefficients; fit-on-the-cut divides it into smaller fits.The method evaluates the integrand on multiple cuts and determines coefficients associated with the corresponding basis sectors.
  • 7 Integrand reduction: FiniteFlow implements full multiloop integrand reduction over finite fields, with outputs reusable for IBP reduction and special-function decomposition.The authors report that this strategy is efficient on complex multiloop integrands, especially relative to the more time-consuming IBP step.
  • 7 Integrand reduction: At higher loops, integrand-basis elements generally require later reduction through integration-by-parts identities, unlike a suitable one-loop basis.The basis choice therefore affects downstream IBP processing.
  • 7 Integrand reduction: Some sectors cannot reach a minimal master-integral basis unless IBP identities use seed integrals with higher denominator powers or additional propagators.The paper cites examples among massive two-loop and some massless four-loop topologies.

8 Decomposition of amplitudes into form factors

FiniteFlow decomposes polarization-stripped amplitudes into tensor structures and computes their rational form factors through numerical contractions and matrix inversion. This avoids explicit analytic expressions for complicated projectors and can also reconstruct helicity amplitudes directly.

  • 8 Decomposition of amplitudes into form factors: A polarization-stripped amplitude is expanded in a basis of tensors compatible with gauge invariance and other known constraints.The free indices may be Lorentz, spinor, or other higher-spin indices.
  • 8 Decomposition of amplitudes into form factors: The form factors are rational functions of kinematic invariants obtained by contracting the amplitude with suitable projectors and applying the inverse tensor matrix.Tensor contractions use full contraction over the relevant indices.
  • 8 Decomposition of amplitudes into form factors: FiniteFlow mitigates two bottlenecks: inversion of the tensor matrix and contraction with complicated projectors.The matrix inversion can be performed numerically as a dataflow-graph node, while simpler contractions T_k·A are multiplied by the inverse later.
  • 8 Decomposition of amplitudes into form factors: The framework reconstructs form factors without requiring explicit analytic projector expressions and can extend the procedure to direct helicity-amplitude reconstruction.This follows by contracting free indices with explicit polarization states.

9 Finding integrable symbols from a known alphabet

FiniteFlow finds integrable symbols from a known alphabet by converting alphabet-dependent derivative relations into numerical linear systems. It then solves integrability recursively from lower to higher weights, while allowing additional constraints to restrict the symbol ansatz.

  • 9 Finding integrable symbols from a known alphabet: A known alphabet supplies the letters used to construct candidate symbols of a specified weight, but arbitrary linear combinations need not be integrable.Integrability is imposed through linear conditions on the symbol coefficients.
  • 9 Finding integrable symbols from a known alphabet: The method depends on explicit letter expressions only through linear relations among crossed derivatives dJ.Once these relations are known, integrability conditions can be solved numerically over Q at any weight.
  • 9 Finding integrable symbols from a known alphabet: FiniteFlow obtains derivative relations with numerical linear fits, replacing independent square roots by auxiliary variables after canonical multilinearization when necessary.For square-root-dependent functions, polynomial remainders modulo r^2−f produce the canonical form.
  • 9 Finding integrable symbols from a known alphabet: Integrable symbols are constructed recursively from lower to higher weights using the complete set of derivative relations.At weight n = 1, every letter is integrable; higher weights impose conditions on the last two entries after lower-weight information is incorporated.
  • 9 Finding integrable symbols from a known alphabet: Additional conditions may further restrict the ansatz and therefore the list of integrable symbols at each weight.The derivative relations alone are sufficient for the stated integrability step, but not necessarily for all symbol constraints.
  • 9 Finding integrable symbols from a known alphabet: The resulting sparse linear system determines relations among ansatz coefficients after dependent derivative structures are eliminated.The procedure substitutes derivative relations and requires coefficients of independent structures to vanish.

10 Proof-of-concept implementation

The proof-of-concept FiniteFlow implementation provides C++ finite-field algorithms, dataflow graphs, functional reconstruction, and a Mathematica interface, together with packages and examples. Its graph-based design supports parallel evaluation, caching, and reusable high-level construction, but the released code is not presented as a final implementation.

  • 10 Proof-of-concept implementation: The released proof-of-concept implementation is written in C++ and includes a high-level Mathematica interface.The Mathematica interface is described as the easiest and most flexible way to use the framework at the time of writing.
  • 10 Proof-of-concept implementation: The authors caution that the code resulted from experimentation and should not be regarded as a final implementation or as meeting high coding standards.They nevertheless report prior use in cutting-edge high-energy-physics results.
  • 10 Proof-of-concept implementation: The release includes Mathematica packages for utilities, IBP systems and differential equations, and integrable symbols, plus runnable examples and templates.These packages are utilities and examples rather than fully automated solutions for specific tasks.
  • 10 Proof-of-concept implementation: The implementation uses finite fields Zp with 63-bit primes and optimized modular arithmetic supported by Flint routines.The framework hard-codes 201 large primes satisfying the stated 62-bit range.
  • 10 Proof-of-concept implementation: Dataflow graphs simplify multithreading because cloning procedures for basic algorithms let the framework automatically clone mutable data for complex graphs.Sessions evaluate graphs, handle parallelization, and run functional reconstruction algorithms.
  • 10 Proof-of-concept implementation: The implementation supports caching and separately evaluating subsets of required points, enabling parallel batches and preservation of intermediate results after crashes or errors.Preliminary univariate reconstructions determine evaluation points for multivariate outputs.
  • 10 Proof-of-concept implementation: FiniteFlow supplies basic finite-field algorithms, functional reconstruction methods, and dataflow-graph infrastructure for defining complex numerical algorithms without low-level coding.The Mathematica interface also provides wrappers for common linear-system and linear-fit tasks.

11 Conclusions

FiniteFlow combines finite-field numerical algorithms, dataflow graphs, and multivariate reconstruction to implement complex algebraic calculations while avoiding large intermediate expressions. Its proof-of-concept implementation has handled diverse, state-of-the-art high-energy-physics problems and supports automated parallelization.

  • FiniteFlow combines low-level finite-field algorithms, dataflow graphs, and multivariate functional reconstruction to represent arbitrarily complex calculations.
  • The framework lets users implement complex calculations in high-level languages and computer algebra systems without managing low-level implementation details.
  • The framework also provides highly automated parallelization to exploit available computing resources.
  • Direct reconstruction of final analytic expressions sidesteps large intermediate expressions, a major bottleneck in complex algebraic calculations.
  • The framework has been applied to highly relevant multi-loop scattering-amplitude problems in high-energy physics.
  • The proof-of-concept implementation tackled both high-scale two-loop five-gluon amplitudes and huge four-loop IBP systems using reasonable computing resources.The examples include two-loop five-gluon helicity amplitudes in Yang–Mills theory and four-loop form-factor reductions to master integrals.

Appendix A Mutability of graphs and nodes

FiniteFlow permits graph and node mutation only while dependency consistency is preserved. Once an object is used downstream, it becomes immutable to prevent invalid evaluations.

  • Mutating nodes or graphs after definition can create inconsistencies between implemented algorithms and their expected inputs.
  • A node may be deleted, replaced, or output-changing metadata may be modified only when no other graph node uses it as input.
  • Once a node is specified as another node’s input, it becomes immutable to preserve downstream evaluation consistency.
  • A graph used as a subgraph becomes immutable, because later mutations could change its output and make the containing graph impossible to evaluate.

Appendix B Further observations on IBP identities

The appendix describes ordering and seed-selection choices for IBP systems, then reports that generalized sector mappings can reduce seed requirements in symmetric kinematics. It also stresses that alternative weight definitions remain possible.

  • Weight ordering: IBP-system unknowns are Feynman integrals, and sparse Gauss elimination complexity depends strongly on their chosen weight ordering.
  • Weight ordering: The customary integral descriptors t, r, and s count positive exponents, sum positive exponents, and negate the sum of negative exponents, respectively.
  • Weight ordering: Higher values of these descriptors generally indicate more complex integrals, while sectors identify integrals sharing the same positive-exponent denominators.
  • Weight ordering: The suggested ordering prioritizes denominator powers no higher than one, but other total-ordering criteria and weight definitions are possible.
  • Seed generation: No a priori minimal seed-integral choice is known, so practical IBP reductions use ranges or other choices expected to work in most cases.
  • Sector mappings: Generalized sector mappings combine external-leg permutations preserving kinematic invariants with optional loop-momentum shifts.
  • Sector mappings: For the two-loop massless double box, including identities for generalized mappings permits reduction for any s range using only seeds with r−t = 0.Without those additional identities, seeds with r−t = 1 are needed.
Loading 1905.08019v2…