GPU Implementation of Zippel Method for Feynman Integral Reconstruction
Alexander V. Smirnov, \orcidID 0000-0002-7779-6735, Boris I.Rozhnov 1 \orcidID 0009-0001-3313-8001, Vadim V. Voevodin 1 \orcidID 0000-0003-1897-1828 · 2025
Read GPU Implementation of Zippel Method for Feynman Integral Reconstruction by Alexander V. Smirnov, \orcidID 0000-0002-7779-6735, Boris I.Rozhnov 1 \orcidID 0009-0001-3313-8001, Vadim V. Voevodin 1 \orcidID 0000-0003-1897-1828 (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-24256.txt.
Introduction
Alexander Smirnov, Boris Rozhnov, and Vadim Voevodin speed up a math method in 2025 by moving it onto graphics processors. The method, named for Zippel, rebuilds formulas from sampled values and shines when most terms are zero. It has become a key step in work on Feynman integrals, the core sums of particle physics.
With many variables, the rebuild can choke the whole job, the team notes. They ported both the classic method and a balanced form for fractions to graphics chips. Tests ran on several such chips to gauge the gain. Graphics chips do many small jobs at once, which suits the method's shape. Faster rebuilds would unblock particle sums that now wait on this one step.
Catalog record
| CREATOR | Alexander V. Smirnov, \orcidID 0000-0002-7779-6735, Boris I.Rozhnov 1 \orcidID 0009-0001-3313-8001, Vadim V. Voevodin 1 \orcidID 0000-0003-1897-1828 |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 28 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-24256
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
GPU Implementation of Zippel Method for Feynman Integral Reconstruction Alexander V. Smirnov, \orcidID 0000-0002-7779-6735, Boris I.Rozhnov 1 \orcidID 0009-0001-3313-8001, Vadim V. Voevodin 1 \orcidID 0000-0003-1897-1828 Abstract The Zippel algorithm performs a rational reconstruction of multivariate polynomials and aims specifically at the sparse case. It is applied in different fields of science, lately becoming an important step in Feynman integral reduction in elementary particle physics. In some cases with multiple variables it might become a bottleneck for the whole evaluation so that different optimizations are required. In this paper we describe how we ported the classical Zippel algorithm together with its balanced version for rational functions to graphical processor units and perform its evaluation on several GPUs. keywords rational reconstruction, Zippel algorithm, Feynman integrals, GPU Introduction The main motivation for this paper lies in the field of elementary particle physics, namely Feynman integral reduction [ 4 ] , one of the key steps of evaluation of Feynman integrals. However a Feynman integral reduction technically means solving a huge sparse linear system with coefficients being rational functions of multiple variables; hence, the scope of the paper and possible applications are much more broad. The classical approach to Feynman integral reduction was to solve the system directly on a large enough server [ 12 , 1 , 14 , 15 , 18 , 24 , 25 , 19 , 17 , 23 , 10 , 11 ] , but with increasing complexity and the availability of a supercomputer infrastructure, new methods were required. Therefore, appeared an approach with a rational reconstruction of functions treating the unknown coefficients as black-box rational functions of multiple variables that have to be reconstructed afterwards [ 20 , 21 , 22 , 9 , 13 , 5 , 16 , 2 ] . Within this ‘‘modular’’ approach the reduction is first performed multiple times with fixed values of variables in modular fields over large prime numbers (fitting into 2^{6}4 to utilize machine-size arithmetics), and then the functions are reconstructed. One should not confuse reconstruction and interpolation; knowing the values of a rational function in multiple points one surely has an unlimited number of rational functions with such properties, but the reconstruction methods are aiming to find such a function that the following probes (evaluations of the function at other points) also match the guessed function. The reconstruction method has a long history starting with Newton interpolation reconstructing a polynomial of one variable. \displaystyle f_{N}(x) \displaystyle={\rm Newton}_{x}[f(x),N] (1) \displaystyle\equiv a_{1}+(x-x_{1})\Big[a_{2}+(x-x_{2})\big[a_{3}+(x-x_{3})\left[a_{4}+\dots\right]\big]\Big]\,. For multivariate polynomial reconstruction one can proceed variable by variable, i.e. when reconstructing from n variables to n+1 variables one takes a needed number of reconstructed functions f(x_{1},x_{2},\ldots,x_{n},x_{n+1,i}) for different values of x_{n+1,i} and runs the univariate Newton reconstruction. For univariate rational functions there is the Thiele reconstruction \displaystyle f_{T}(x) \displaystyle={\rm Thiele}_{x}[f(x),T] (2) \displaystyle\equiv b_{0}+(x-x_{1})\left[b_{1}+(x-x_{2})\left[b_{2}+(x-x_{3})\left[b_{4}+\dots\right]^{-1}\right]^{-1}\right]^{-1}\,. The situation becomes more complicated with multivariate rational functions since the recursive Thiele formula is a combination of continued fractions and is technically too complex to be evaluated in real examples. Therefore, for multivariate rational functions, other methods are used, one of those being the balanced Newton reconstruction proposed in [ 2 ] and the balanced Zippel reconstruction proposed in [ 26 ] for sparse multivariate functions. The balanced Zippel reconstruction of rational functions is the main subject of this paper. It is based on the Zippel reconstruction of polynomials suggested initially in [ 28 ] and developed in [ 3 , 8 ] . The Zippel method is an approach with the lowest complexity for the sparse polynomial reconstruction. It is already widely applied in programs for Feynman integral reduction using the modular approach with the following reconstruction. However, for some cases, the Zippel reconstruction itself might become a bottleneck for the whole approach due to its quadratic complexity by the number of terms in the skeleton polynomial (see next section for details) which might be measured in millions. Hence any possible optimization of the Zippel algorithm is needed. There is a number of public Zippel algorithm implementations, mostly in some open-source repositories. Speaking of its applications to Feynman algorithms, programs such as Kira or FIRE use the Zippel algorithm. The main contribution of this paper is an implementation of the Zippel algorithm on GPUs (Graphical Processing Units). According to our information, this is the first such implementation of this algorithm on GPUs. Currently we publish a description and evaluation results, while the code is in a private repository related to Feynman integrals, but we intend to make it public as a part of the new FIRE version this year. We are also considering a possible separation of the modular GPU and reconstruction part providing it as a separate library. The rest of the paper is organized as follows. Section 1 describes the original Zippel algorithm. Section 2 is devoted to our implementation of this algorithm on GPUs. Section 3 provides evaluation results and benchmarks. 1 Description of Zippel Method The Zippel method is a reconstruction procedure from a polynomial with k-1 variables to a polynomial with k variables. The traditional approach for dense polynomials (meaning that if one considers all possible monomials of a given degree most of the coefficients are non-zero) is to proceed with a Newton reconstruction formula. However for sparse polynomials this is quite inefficient because it requires a large number of probes for the reconstruction. Let us remind the method taking a few formulas from our paper [ 26 ] . Suppose that we have already reconstructed a polynomial f(x_{1},\ldots,x_{k-1},c_{0}) , where c_{0} is some constant value of x_{k} . There might be more variables, but they should be fixed at this point. We aim to run the Newton reconstruction for x_{k} , so we need similar reconstructed polynomials for other values of x_{k} . Suppose we take another value c_{i} of x_{k} . We consider the existing polynomial f(x_{1},\ldots,x_{k-1},c_{0},\ldots) as a skeleton, take all its non-zero monomials and assume that the set of nonzero monomials will remain the same for the yet unknown f(x_{1},\ldots,x_{k-1},c_{i},\ldots) so that it can have the following form: f(x_{1},\ldots,x_{k-1},c_{i},\ldots)=a_{1}\cdot x_{1}^{p_{1},1}\ldots{x_{k-1}}^{p_{k-1,1}}+\ldots+a_{t}\cdot x_{1}^{p_{1},t}\ldots{x_{k-1}}^{p_{k-1,t}} (3) for some t , where a_{i} are unknown constant coefficients and p are exponents taken from the skeleton. This is a linear system for a_{i} and hence knowing the values of f(x_{1},\ldots,x_{k-1},c_{i},\ldots) for t different sets of \{x_{1},\ldots,x_{k-1}\} (sampling points or probes) we can solve the system. This however has a complexity O(t^{3}) , thus the Zippel algorithm for polynomials suggests a specific set of sampling points, i.e. {y_{1},...y_{k-1}},{y_{1}^{2},...y_{k-1}^{2}},\ldots,{y_{1}^{t},...y_{k-1}^{t}} . In this case the system turns into a Vandermonde system which can be solved with complexity O(t^{2}) . The Zippel method consists of solving this system leading to the knowledge of f(x_{1},\ldots,x_{k-1},c_{i},\ldots) for different i , followed by univariate Newton reconstruction in x_{k} to obtain f(x_{1},\ldots,x_{k-1},x_{k},\ldots) . For the tasks described one needs to reconstruct rational functions of multiple variables, but it is possible to adapt the Zippel approach, for example, as the balanced Zippel method described in [ 26 ] . What is also important for the proper reconstruction order is to perform it in modular arithmetic over large prime numbers. This prevents coefficient growth and decreases the number of needed sampling points, and the final reconstruction to rational numbers