GPU Implementation of Zippel Method for Feynman Integral Reconstruction

Alexander V. Smirnov; Boris I. Rozhnov; Vadim V. Voevodin

doi:10.14529/jsfi250202

Authors

Alexander V. Smirnov Lomonosov Moscow State University, Moscow, Russian Federation https://orcid.org/0000-0002-7779-6735
Boris I. Rozhnov Lomonosov Moscow State University, Moscow, Russian Federation https://orcid.org/0009-0001-3313-8001
Vadim V. Voevodin Lomonosov Moscow State University, Moscow, Russian Federation https://orcid.org/0000-0003-1897-1828

DOI:

https://doi.org/10.14529/jsfi250202

Keywords:

rational reconstruction, Zippel algorithm, Feynman integral, GPU

Abstract

The Zippel algorithm performs a rational reconstruction of multivariate polynomials and aims specifically at the sparse case, where other approaches, such as iterative Newton and Thiele reconstructions, have a significantly higher complexity. It is applied in different fields of science, lately becoming an important step in Feynman integral reduction in elementary particle physics within the modular approach to reduction. For some cases with multiple variables the Zippel reconstruction 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 for polynomials together with its balanced version for rational functions to graphical processor units (GPUs), as well as carried out its performance evaluation on several types of GPUs. According to our information, this is the first publically available implementation of this algorithm on GPUs, and the results show speedup up to 14.5 times compared to CPU-based version.

References

Anastasiou, C., Lazopoulos, A.: Automatic integral reduction for higher order perturbative calculations. Journal of High Energy Physics 07, 046 (2004). https://doi.org/10.1088/1126-6708/2004/07/046

Belitsky, A.V., Smirnov, A.V., Yakovlev, R.V.: Balancing act: Multivariate rational reconstruction for IBP. Nucl. Phys. B 993, 116253 (2023). https://doi.org/10.1016/j.nuclphysb.2023.116253

Ben-Or, M., Tiwari, P.: A deterministic algorithm for sparse multivariate polynomial interpolation. In: Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing. p. 301–309. STOC ’88, Association for Computing Machinery, New York, NY, USA (1988). https://doi.org/10.1145/62212.62241

Chetyrkin, K.G., Tkachov, F.V.: Integration by Parts: The Algorithm to Calculate beta Functions in 4 Loops. Nucl. Phys. B 192, 159–204 (1981). https://doi.org/10.1016/0550-3213(81)90199-1

De Laurentis, G., Page, B.: Ans¨atze for scattering amplitudes from p-adic numbers and algebraic geometry. Journal of High Energy Physics 12, 140 (2022). https://doi.org/10.1007/JHEP12(2022)140

Hart, W.: Fast Library for Number Theory: An introduction. In: Fukuda, K., van der Hoeven, J., Joswig, M., Takayama, N. (eds.) Mathematical Software – ICMS 2010. Lecture Notes in Computer Science, vol. 6327, pp. 88–91. Springer (2010). https://doi.org/10.1007/978-3-642-15582-6_15

Hart, W., Johansson, F., Schultz, D., et al.: FLINT: Fast Library for Number Theory. http://www.flintlib.org/, version 2.9 (or your version), accessed: 2025-05-01

Kaltofen, E., Lee, W.s., Lobo, A.A.: Early termination in Ben-Or/Tiwari sparse interpolation and a hybrid of Zippel’s algorithm. In: Proceedings of the 2000 International Symposium on Symbolic and Algebraic Computation. p. 192–201. ISSAC ’00, Association for Computing Machinery, New York, NY, USA (2000). https://doi.org/10.1145/345542.345629

Klappert, J., Lange, F.: Reconstructing rational functions with FireFly. Comput. Phys. Commun. 247, 106951 (2020). https://doi.org/10.1016/j.cpc.2019.106951

Klappert, J., Lange, F., Maierh¨ofer, P., et al.: Integral reduction with Kira 2.0 and finite field methods. Comput. Phys. Commun. 266, 108024 (2021). https://doi.org/10.1016/j.cpc.2021.108024

Lange, F., Usovitsch, J., Wu, Z.: Kira 3: integral reduction with efficient seeding and optimized equation selection (2025), https://arxiv.org/abs/2505.20197

Laporta, S.: High precision calculation of multiloop Feynman integrals by difference equations. Int. J. Mod. Phys. A 15, 5087–5159 (2000). https://doi.org/10.1142/S0217751X00002159

Laurentis, G., Maˆıtre, D.: Extracting analytical one-loop amplitudes from numerical evaluations. Journal of High Energy Physics 07, 123 (2019). https://doi.org/10.1007/JHEP07(2019)123

Lee, R.N.: Presenting LiteRed: a tool for the Loop InTEgrals REDuction (12 2012)

Lee, R.N.: LiteRed 1.4: a powerful tool for reduction of multiloop integrals. J. Phys. Conf. Ser. 523, 012059 (2014). https://doi.org/10.1088/1742-6596/523/1/012059

Magerya, V.: Rational Tracer: a Tool for Faster Rational Function Reconstruction (11 2022)

Maierh¨ofer, P., Usovitsch, J.: Kira 1.2 Release Notes (12 2018)

Maierh¨ofer, P., Usovitsch, J., Uwer, P.: Kira A Feynman integral reduction program. Comput. Phys. Commun. 230, 99–112 (2018). https://doi.org/10.1016/j.cpc.2018.04.012

von Manteuffel, A., Studerus, C.: Reduze 2 – Distributed Feynman Integral Reduction (2012), https://arxiv.org/abs/1201.4330

von Manteuffel, A., Schabinger, R.M.: A novel approach to integration by parts reduction. Phys. Lett. B 744, 101–104 (2015). https://doi.org/10.1016/j.physletb.2015.03.029

Peraro, T.: Scattering amplitudes over finite fields and multivariate functional reconstruction. Journal of High Energy Physics 12, 030 (2016). https://doi.org/10.1007/JHEP12(2016)030

Peraro, T.: FiniteFlow: multivariate functional reconstruction using finite fields and dataflow graphs. Journal of High Energy Physics 07, 031 (2019). https://doi.org/10.1007/JHEP07(2019)031

Smirnov, A.V., Chuharev, F.S.: FIRE6: Feynman Integral REduction with Modular Arithmetic. Comput. Phys. Commun. 247, 106877 (2020). https://doi.org/10.1016/j.cpc.2019.106877

Smirnov, A.V., Smirnov, V.A.: FIRE4, LiteRed and accompanying tools to solve integration by parts relations. Comput. Phys. Commun. 184, 2820–2827 (2013). https://doi.org/10.1016/j.cpc.2013.06.016

Smirnov, A.V.: FIRE5: a C++ implementation of Feynman Integral REduction. Comput. Phys. Commun. 189, 182–191 (2015). https://doi.org/10.1016/j.cpc.2014.11.024

Smirnov, A.V., Zeng, M.: Feynman integral reduction: balanced reconstruction of sparse rational functions and implementation on supercomputers in a co-design approach. Numerical Methods and Programming 25(Special issue), 30–45 (2024). https://doi.org/10.26089/NumMet.2024s03

Voevodin, V., Antonov, A., Nikitenko, D., et al.: Supercomputer Lomonosov-2: Large Scale, Deep Monitoring and Fine Analytics for the User Community. Supercomputing Frontiers and Innovations 6(2), 4–11 (2019). https://doi.org/10.14529/jsfi190201

Zippel, R.: Probabilistic algorithms for sparse polynomials. In: Ng, E.W. (ed.) Symbolic and Algebraic Computation. pp. 216–226. Springer Berlin Heidelberg, Berlin, Heidelberg (1979)