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

Precise predictions for complex scattering processes depend on algebraic calculations whose complexity grows with loop order, particle count, and physical scales. FiniteFlow combines numerical algorithms over finite fields in dataflow graphs and reconstructs analytic expressions from numerical evaluations. The paper demonstrates the framework on multi-loop scattering-amplitude problems.

  • Problem

    Precise predictions for complex scattering processes rely on algebraic calculations whose complexity depends on loop order, particle count, and physical scales.

    Source: §1 · p. 3

  • Method

    FiniteFlow combines numerical algorithms over finite fields in dataflow graphs and reconstructs analytic expressions from numerical evaluations.

    Source: §11 · p. 47

  • Results

    The paper demonstrates FiniteFlow on highly relevant problems involving the calculation of multi-loop scattering amplitudes.

    Source: §11 · p. 47

  • Takeaways & Limitations

    The framework reconstructs final analytic expressions while sidestepping large intermediate expressions identified as a major bottleneck.

    Source: §11 · p. 47

    In integrand reduction, the described method may not yield a complete minimal master-integral basis when higher-power or additional-propagator seed integrals are needed.

    Source: §7.3 · p. 38

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 reconstructs analytic rational expressions from finite-field evaluations while letting users build complex numerical calculations from reusable components. Its dataflow-graph framework combines efficient low-level algorithms with high-level usability and parallel evaluation.

Motivation and approach

  • Large intermediate expressions can overwhelm analytic calculations, while finite-field evaluations enable exact, machine-integer arithmetic and reconstruction of multivariate rational functions from samples.This reduces rational-function computation to efficient numerical evaluation, which can be massively parallelized.Source: §1 · p. 3
  • FiniteFlow addresses the lack of a public arbitrary-multivariate reconstruction implementation and the difficulty of efficiently implementing evaluation algorithms in low-level languages.Combining reusable building blocks avoids limiting reconstruction to hardcoded algorithms that may capture only intermediate calculation steps.Source: §1 · p. 4

Framework

  • FiniteFlow combines low-level finite-field algorithms into dataflow graphs, enabling complex calculations and rational-function reconstruction without requiring users to write low-level code.Graph nodes represent basic algorithms whose inputs can be outputs of other nodes; evaluations can be automated and parallelized across computing resources.Source: §1 · pp. 4–5

Reconstruction algorithm

  • The paper presents an improved reconstruction algorithm [2], using a dense approach distinct from the sparse multivariate algorithm published during its preparation.Source: §1 · pp. 4–5

Novelty and implementation

  • The authors describe dataflow graphs as a first application to finite-field rational algorithms and release a proof-of-concept C++ framework with a Mathematica interface.They provide public codes and examples for common high-energy-physics problems.Source: §1 · p. 5

2 Finite fields and functional reconstruction

This section explains how rational functions can be evaluated and reconstructed from finite-field black-box samples, then organized for parallel execution.

2.1 Finite fields and rational functions

  • Prime fields Zp support rational operations, while Chinese-remainder combination of several primes supplies enough modulus for Wang’s algorithm to reconstruct rational coefficients, which are checked on unused fields.The reconstruction continues with additional primes if those checks fail, stopping when the rational result agrees with evaluations over fields not used in reconstruction.Source: §2.1 · pp. 6–7

2 Finite fields and functional reconstruction

  • The black-box method infers an unknown multivariate rational function from finite-field evaluations, replacing failed or singular evaluations with new sample points.The framework’s reconstruction algorithm follows the strategy in with modifications and improvements; sample points are chosen to make singular evaluations unlikely in realistic problems.Source: §2.2 · p. 7

2.2 Multivariate functional reconstruction

  • Multivariate rational reconstruction rescales arguments with auxiliary t, reconstructs its univariate rational form, then recursively recovers homogeneous polynomial coefficients, efficiently handling complex functions without huge dense ansatz systems.Initial univariate fits estimate degrees and factor out polynomial prefactors; cached evaluations and reconstructing lower-degree polynomials first reduce later systems. Shifting the arguments makes the denominator’s constant term non-vanishing, fixing coefficient normalization.Source: §2.2 · pp. 9–10

2.3 Parallelization

  • For multivariate problems, independent evaluations and n + 1 preliminary univariate reconstructions can be parallelized, with minimal synchronization and no dependence on the numerical algorithm.The strategy may oversample slightly to prepare evaluation points in advance; parallel reconstruction of separate output functions can also improve performance. Univariate reconstruction is not parallelized by default, though an automated option uses degree guesses and adds evaluations if needed.Source: §2.3 · pp. 11–12

3 Dataflow graphs

FiniteFlow builds numerical algorithms over finite fields using dataflow graphs, providing a flexible, performant, and easy-to-use way to implement rational-function calculations. The graphs combine reusable numerical algorithms and can embed other graphs.

3.1 Graphs as numerical procedures

  • Complex calculations are assembled from reusable numerical nodes in a dataflow graph, which can be defined from a high-level language without handling low-level implementation details.Graphs are directed acyclic structures whose nodes consume lists of values and produce one list of fixed length; evaluation proceeds from lower to higher node depths.Source: §3.1 · p. 13

3.2 Learning nodes

  • Nodes can use a learning phase to determine their output before other nodes can consume it, addressing algorithms whose output length is not known when the graph is defined.For example, a linear-system solver's output length can depend on whether the system is determined and on its rank, which can be learned through numerical evaluations.Source: §3.2 · p. 14

3.3 Subgraphs

  • Nodes can embed subgraphs, including memoized subgraphs that reuse stored outputs for repeated inputs and subgraph maps that evaluate the same graph on multiple inputs.Simple subgraphs also help organize complicated graphs; memoization can avoid reevaluating parts that depend only on variables held fixed across evaluations.Source: §3.3 · p. 14

4 Numerical algorithms over finite fields

This section presents numerical algorithms that serve as building blocks for dataflow graphs and more complex calculations. It covers graph nodes for list and matrix manipulation, Laurent expansion of rational-function outputs, and algorithms that depend only on the prime field.

4.1 Evaluation of rational functions

  • Rational-function nodes evaluate polynomial ratios at input values, using Horner’s scheme in R multiplications and R additions for a degree-R polynomial.For multivariate polynomials, the scheme is applied recursively but implemented non-recursively, with coefficients and sub-polynomial degree metadata stored contiguously; a zero denominator makes an evaluation a singular point.Source: §4.1 · p. 15

4.2 Dense and sparse linear solvers

  • Dense systems use Gauss elimination, while sparse systems use complexity-ordered elimination to keep equations simple, with scaling ranging from O(n) in the best case to O(n3) in the worst.The learning phase identifies dependent and independent unknowns, removes redundant equations, and flags evaluations where accidental zeroes change the solution structure; optional mark-and-sweep can further discard equations not needed for requested unknowns.Source: §4.2 · pp. 16–19

4.3 Linear fit

  • Subgraph-fit nodes find linear relations among graph outputs, allowing complex entries to be expressed through simpler ones so only independent entries need reconstruction.For each z, linear fits sample τ at m+nchecks points, typically with nchecks = 2; auxiliary functions and numerical weights support flexible fits, including integrand reduction. Subgraph multi-fit generalizes this to lists of output indices, can share graph evaluations, and can use a guessed rational-function basis to reduce reconstruction to z variables or numerical reconstruction when z is empty.Source: §4.3 · pp. 20–22

4.4 Basic operations on lists and matrices

  • Basic list and matrix operations are fast utilities for combining algorithm outputs; the described Take operation selects specified elements from any number of input lists.These simple operations expand the flexibility of graph-based algorithms.Source: §4.4 · p. 22
  • List and matrix nodes support chaining and slicing lists, dense or sparse matrix multiplication, tensor contractions, and extraction of nonzero outputs to reduce reconstruction memory use.The Non-Zeroes node learns which entries vanish through numerical evaluations before returning only nonzero elements.Source: §4.4 · pp. 22–23

4.5 Laurent expansion

  • A Laurent-expansion node reconstructs a graph’s output in ϵ at fixed z values, detects overall ϵ prefactors, and returns coefficients through specified truncation orders.Its learning phase identifies numerator and denominator degrees using Thiele’s formula; subsequent evaluations use univariate system solving, with graph evaluations cached for reuse.Source: §4.5 · pp. 23–24

4.6 Algorithms with no input

  • Input-free nodes depend only on the prime field Zp, and input-free graphs represent purely numerical rational algorithms reconstructed using Wang’s algorithm and the Chinese remainder theorem.Examples include linear-system solutions, linear fits without free parameters, and evaluation of rational-number lists.Source: §4.6 · p. 24

5 Reduction of scattering amplitudes

The section presents reducing scattering amplitudes to master integrals or special functions as a major application of finite-field functional reconstruction. Dataflow graphs support numerical evaluation and analytic reconstruction of the resulting coefficients.

5.1 Integration-by-parts reduction to master integrals

  • IBP, Lorentz-invariance, symmetry, and mapping relations form a sparse linear system whose solution reduces integrals to master integrals selected during the solver’s learning phase.The ordering of unknown integrals can be specified and affects solver efficiency; the master-integral list is determined after only a few numerical evaluations.Source: §5.1 · pp. 25–26
  • Numerical evaluation of a small dataflow graph reconstructs amplitude-to-master-integral coefficients analytically, avoiding large analytic IBP tables that can be impractical to compute and use.The graph combines unreduced-amplitude coefficients with numerical IBP solutions; its output node performs the matrix multiplication. Prior reductions used this approach.Source: §5.1 · pp. 26–28

5.2 Reduction to special functions and Laurent expansion in ϵ

  • The special-function route extends the master-integral graph with rational function-basis coefficients, then uses a Laurent-expansion node to compute amplitude coefficients in ϵ.Subgraph fitting can find linear relations among these coefficients, while analytic renormalization or infrared-subtraction terms can be added to simplify reconstruction; the strategy also applies to correlation functions and form factors.Source: §5.2 · pp. 28–29

6 Differential equations for master integrals

This section applies finite-field functional reconstruction to master-integral differential equations, including ϵ-form systems and bases involving square-root prefactors.

6.1 Reconstructing differential equations

  • The dataflow graph reconstructs master-integral differential equations by differentiating masters analytically, reducing derivatives through IBP, and multiplying reduction coefficients, avoiding analytic IBP tables.The calculation is analogous to amplitude reduction and usually substantially simplifies the calculation.Source: §6.1 · p. 30

6.2 Differential equations in ϵ-form

  • For UT master integrals, differential-equation matrices have an overall ϵ factor; numerical checks of the quotient verify ϵ-form, whose simpler structure favors functional reconstruction.The check evaluates the modified graph at several ϵ values while keeping the invariants fixed.Source: §6.2 · pp. 31–32
  • When a topology’s alphabet is known, logarithmic-letter derivatives provide a basis for linearly fitting rational matrix coefficients.A subgraph multi-fit performs the fit, and Wang’s algorithm with the Chinese remainder theorem reconstructs its output over Q.Source: §6.2 · p. 32

6.3 Differential equations with square roots

  • For square-root-prefactored UT masters, reconstructing the rational matrix from a root-free quantity and restoring prefactors works without more general finite fields; the matrix remains in ϵ-form.The root-free quantity can be reduced through IBP because the logarithmic derivative of a square root of a rational function is rational.Source: §6.3 · p. 33

7 Integrand reduction

Integrand reduction provides an efficient way to express amplitudes in a standard form for complex processes, supplying coefficients needed for later reduction to master integrals or special functions. The section describes finite-field dataflow implementations, basis choices, and how to represent the integrand compactly.

7.1 Integrand reduction via linear fits

  • Fit-on-the-cut linear fits determine process-dependent coefficients in a topology-chosen integrand basis, proceeding from maximal cuts downward and subtracting previously determined on-shell terms.Each cut can be implemented as a dataflow node that uses higher-point cut outputs for subtraction; auxiliary functions allow numerical cut substitutions without expanding the full integrand. The resulting coefficients feed later reduction stages, and the authors report this strategy is efficient even for complex multiloop integrands.Source: §7.1 · pp. 34–36

7.2 Choice of an integrand basis

  • At one loop, a basis can yield known integrals without IBP, while a recommended multiloop choice uses parent-topology denominators and auxiliaries to produce integrals suited to standard IBP reduction.For fewer than five external legs, the basis also includes scalar products with vectors orthogonal to the external momenta; these can be integrated out by tensor decomposition or angular integration.Source: §7.2 · pp. 36–37
  • Surface-term bases embed IBP reduction into integrand reduction, but can complicate the fit, introduce regulator dependence, and yield incomplete reductions when additional seed integrals are needed.The cited limitation applies when full reduction requires seed integrals with higher denominator powers or more propagators than those in the diagrams, including some massive two-loop and massless four-loop topologies.Source: §7.2 · p. 37, §7.3 · p. 38

7.3 Writing the integrand

  • Four-dimensional external spinors, polarization vectors, and momenta admit rational parametrization by momentum-twistor variables; loop-dependent objects can instead be substituted numerically through auxiliary functions, keeping integrands compact.Source: §7.3 · pp. 38–39

8 Decomposition of amplitudes into form factors

FiniteFlow can support amplitude decomposition into rational form factors by evaluating contractions and matrix operations numerically, avoiding complicated analytic projectors. The same approach can reconstruct helicity amplitudes directly when explicit polarization states are used.

8 Decomposition of amplitudes into form factors

  • The method strips external polarization states, expands the amplitude in tensors compatible with its constraints, and computes rational form factors using suitable projectors.The free indices may be Lorentz, spinor, or higher-spin indices.Source: §8 · p. 39
  • FiniteFlow addresses matrix inversion and complicated projector contractions; numerical inversion can be represented in the dataflow graph and takes negligible time compared with tasks such as IBP reduction.A dense solver is typically suitable when the tensor basis lacks special orthogonality properties.Source: §8 · p. 40
  • Instead of explicit projectors, one can compute contractions T_k·A, multiply them numerically by the inverse matrix later, and reconstruct form factors or helicity amplitudes directly.Helicity amplitudes are obtained by contracting the free indices with explicit polarization states.Source: §8 · p. 40

9 Finding integrable symbols from a known alphabet

Given a known alphabet, the section presents a procedure for constructing complete sets of integrable symbols up to a chosen weight by solving linear integrability constraints.

Finding integrable symbols

  • A symbol is integrable exactly when its coefficients satisfy the stated conditions for every adjacent pair of entries and pair of kinematic variables; solving them gives a linear system.Additional entry restrictions, such as allowing only letters associated with physical branch points in the first entry, can further restrict the symbol ansatz.Source: §9 · pp. 40–41
  • Precomputing linear relations among crossed derivatives for an alphabet lets the integrability conditions be solved at any weight using a numeric linear system over Q, without reusing the letters’ analytic expressions.The relations can be found by analytically computing the derivatives and fitting them, with obvious relations such as zero or sign-opposite pairs extracted beforehand.Source: §9 · p. 41
  • For independent square roots, the method canonicalizes each derivative to be multilinear in the roots, then treats each root as an independent variable in the linear fit.The passage notes this can be more efficient even when the roots are rationalizable.Source: §9 · pp. 41–42
  • Recursively extending lower-weight integrable symbols yields a smaller ansatz; imposing the remaining conditions with derivative relations produces a sparse linear system for the coefficients.Other restrictions may still constrain the ansatz at each weight.Source: §9 · p. 42

10 Proof-of-concept implementation

Section 10 describes a publicly released proof-of-concept FiniteFlow implementation in C++ with a high-level Mathematica interface, plus its implementation choices and parallel-execution options. It presents dataflow graphs as a flexible way to define algorithms for varied algebraic problems.

10 Proof-of-concept implementation

  • The public proof-of-concept release includes a high-level Mathematica interface, packages, and examples, but is not presented as a final implementation or as fully automated solutions for specific tasks.The authors report that the code has already been used for cutting-edge high-energy-physics results and describe the packages and examples as utilities and templates for further work.Source: §10 · pp. 42–43
  • FiniteFlow is implemented in C++ and uses 63-bit prime fields; its Mathematica interface is currently the easiest and most flexible way to combine the framework with a computer algebra system.The implementation uses primes between 2^62 and 2^63 and different polynomial and rational-function representations depending on the task, including contiguous arrays for repeated evaluation and sparse polynomials for other operations.Source: §10 · pp. 43–44
  • Dataflow graphs let users define complex numerical algorithms without low-level coding, support custom C++ algorithms, and are intended for a wide variety of algebraic problems.The framework can automatically clone mutable data for multithreaded graph evaluations; graph serialization is described as a potential advantage, but is not implemented.Source: §10 · pp. 45–46
  • Caching tags each output element with the evaluation points needed for its reconstruction and stores only those entries per point, reducing memory use when outputs are long and element complexities vary.The authors report that combined with Non-Zeros nodes, this makes evaluation caching hardly ever a memory bottleneck in their realistic scenarios.Source: §10 · p. 45

10.1 Parallel execution

  • 10.1 offers automatic multithreading and a distributed strategy that shares evaluation-point lists across machines, computes subsets independently, and gathers results for reconstruction.If reconstruction needs more prime fields, users generate and evaluate complementary point lists; this strategy is less automated but can also split long calculations into batches and save intermediate results.Source: §10.1 · pp. 46–47

11 Conclusions

FiniteFlow combines finite-field numerical algorithms, dataflow graphs, and multivariate reconstruction to obtain analytic results from complex algebraic calculations. The paper demonstrates applications to multi-loop scattering amplitudes and releases a proof-of-concept implementation.

11 Conclusions

  • FiniteFlow combines efficient finite-field algorithms, dataflow graphs for complex calculations, and multivariate reconstruction of analytic results.The graphs let users combine basic algorithms into arbitrarily complex computational procedures.Source: §11 · p. 47
  • High-level languages and computer algebra systems can define calculations without handling low-level implementation details, while automated parallelization uses available computing resources.Reconstructing final analytic expressions directly also sidesteps large intermediate expressions, a typical bottleneck.Source: §11 · p. 47
  • The framework is applied to highly relevant high-energy physics problems, particularly multi-loop scattering-amplitude calculations.The paper also describes applications to a wide variety of algebraic problems across several fields.Source: §11 · p. 47
  • The released proof-of-concept implementation handles state-of-the-art problems beyond traditional computer algebra using reasonable computing resources.Examples include two-loop five-gluon helicity amplitudes in Yang-Mills theory and four-loop form-factor reduction to master integrals. Their complexity arises respectively from many scales and huge IBP systems, demonstrating a broad problem range.Source: §11 · p. 47
  • The authors expect the algorithms and publicly released implementation to help push the limits of algebraic calculations and support future scientific results.They attribute this potential to the framework’s efficiency and flexibility.Source: §11 · pp. 47–48
  • A possible future extension is MPI-based parallel evaluation across cluster nodes, but it would be more limiting than the implemented approach.The footnote notes that MPI does not support parallelization across unrelated machines.Source: §11 · p. 47

Appendix A Mutability of graphs and nodes

FiniteFlow permits mutations to graphs and nodes when they remain consistent, but freezes nodes or graphs once they are used as inputs or subgraphs to prevent evaluation failures.

Appendix A Mutability of graphs and nodes

  • Mutating already-defined graphs or nodes can create inconsistencies, so the implementation allows mutations only to the extent that defined graphs remain consistent.The appendix describes mutability as a technical implementation aspect whose usefulness depends on the use case.Source: Appendix A · p. 48
  • Nodes may be deleted, replaced, or have output-changing metadata modified only while no other node uses them as input.After dependent nodes are deleted, the node becomes mutable again.Source: Appendix A · p. 48
  • A graph becomes immutable when used as a subgraph, because changing it could alter its output and make the containing graph impossible to evaluate.Its output node is also made immutable; the graph becomes mutable again after all nodes using it as a subgraph are deleted.Source: Appendix A · p. 48

Appendix B Further observations on IBP identities

The appendix gives practical guidance for ordering and generating IBP systems, and identifies identities that can be missed for generalized sector mappings. Its recommendations balance system size against successful reduction.

Weight ordering

  • The proposed integral ordering prioritizes denominator powers no higher than one and can reduce needed equations with mark-and-sweep, though other weight definitions are possible.Weight choice affects sparse Gauss-elimination complexity; the authors found this ordering particularly effective with mark-and-sweep filtering.Source: Appendix B · pp. 48–50

Seed selection

  • For most topologies, seed integrals with r −t equal to the maximum needed-integral value or one higher are often sufficient, and mark-and-sweep may filter excess equations.There is no known a priori minimal seed choice, and whether excess equations are filtered depends on the integral ordering; the suggested weight ordering showed this behavior empirically.Source: Appendix B · p. 50

Sector mappings

  • Generalized mappings can leave independent IBP, Lorentz, or sector-symmetry identities uncovered, so the authors recommend generating those identities for mapped sectors as well.In the two-loop massless double box, r −t = 0 seeds suffice for any s range when these identities are included; without them, r −t = 1 seeds are needed. The authors also recommend always adding Lorentz invariance identities.Source: Appendix B · pp. 50–51

Related papers

Loading 1905.08019v2…