LinApart2 : efficient parallel partial fraction decomposition algorithm for denominators with polynomials of general degree

L. Fekésházy, O. Schnetz · 2025

Read LinApart2 : efficient parallel partial fraction decomposition algorithm for denominators with polynomials of general degree by L. Fekésházy, O. Schnetz (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-2511-15735.txt.

Introduction

Levente Fekésházy and Oliver Schnetz present LinApart2, a major update of a program for partial fraction decomposition. That algebraic task rewrites a rational function, a ratio of polynomials, as a sum of simpler fractions, a step needed in many symbolic calculations. The earlier version struggled with denominators that are high-degree polynomials unless they were factored first.

The new version handles denominators of arbitrary degree without explicit factorization, while keeping the speed and parallel structure of its Laurent series method. Series expansions around chosen points carry the needed information. Benchmarks show major gains in run time and memory over a leading commercial routine and over the classic Euclidean algorithm, enabling computations that were previously out of reach.

Catalog record

CREATORL. Fekésházy, O. Schnetz
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE39 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2511-15735

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

LinApart2 : efficient parallel partial fraction decomposition algorithm for denominators with polynomials of general degree L. Fekésházy, O. Schnetz Abstract We present LinApart2 , a major update to the LinApart algorithm for univariate partial fraction decomposition. Unlike its predecessor, LinApart2 can handle denominators of arbitrary polynomial degree without explicit factorization, while retaining the efficiency and parallelizability of the Laurent series method. Benchmarks show substantial speedups in both runtime and memory usage compared to Mathematica ’s built-in routine Apart and to the Euclidean algorithm, enabling computations that were previously intractable. \newpageafter abstract PROGRAM SUMMARY Program title: LinApart CPC Library link to program files: Developer’s repository link: https://github.com/fekeshazy/LinApart Licensing provisions: MIT license (MIT) Programming language: Wolfram Mathematica Supplementary material: Nature of the problem: Analytic computations in Quantum Field Theory frequently yield large expressions involving complex rational functions. In many applications, such as symbolic integration or series expansion, partial fraction decomposition is essential. While univariate partial fraction decomposition is conceptually well-understood and an efficient algorithm exist for linear denominators, there has been no publicly available tool capable of efficiently handling denominator polynomials of higher degree. Here, we present LinApart2 , a routine designed to perform univariate partial fraction decomposition in a parallel and highly efficient manner for denominator polynomials of arbitrary degree. Our benchmarks demonstrate significant improvements in timing and memory usage by orders of magnitude for rational expressions with only a few denominator factors. As a result, LinApart2 enables the decomposition of problems that were previously intractable. Solution method: The LinApart2 routine extends the Laurent series method for univariate partial fraction decomposition of rational functions using elements of Galois theory. The Mathematica implementation leverages the highly efficient built-in extended polynomial greatest common divider routine and repeated replacement routines to perform the necessary operations. Additional comments including Restrictions and Unusual features: LinApart2 preserves the user interface and options of the original version, while introducing parallelization for linear denominators as well. References: 8 1 Introduction Partial fraction decomposition (PFD) is a fundamental computational tool in modern perturbative Quantum Field Theory (QFT) calculations, where the increasing complexity of multi-loop and multi-scale problems demands ever more efficient algorithms. Primarily, PFD plays a crucial role in two contexts: simplifying expressions after Integration-By-Parts (IBP) reduction 12 , 4 , 5 , 2 , 3 , 15 , and preparing integrands for analytic integration in terms of special functions such as multiple polylogarithms 14 , 19 , 13 , 1 , 11 , 7 , 18 . In the latter application, partial fraction decomposition is essential for casting integrals into forms recognizable as iterated integrals. Furthermore, direct symbolic computation of phase-space integrals relevant for building subtraction schemes beyond next-to-leading order can lead to expressions where the efficiency of standard partial fraction decomposition routines becomes a bottleneck 21 , 6 , 22 , 10 , 9 . Although univariate partial fraction decomposition is a well-studied problem with numerous algorithmic solutions 24 , 17 , 23 , 16 , the computational demands of contemporary QFT calculations have exposed significant performance limitations of the aforementioned methods. The two most widely implemented approaches are the equation system method and the Euclidean algorithm. However, they suffer from serious scaling problems and offer limited possibility for parallelization. These bottlenecks become particularly acute when dealing with high-degree polynomials, when denominator polynomials are raised to high powers (multiplicities), or when the denominator has many polynomials. The Laurent series method, introduced in our previous work 8 , addressed these performance concerns by reformulating partial fraction decomposition in terms of a Laurent series calculation. This approach offers two key advantages: first, the residues at different poles can be computed independently, enabling straightforward parallelization; second, the method avoids the polynomial arithmetic bottlenecks in traditional algorithms. However, the original LinApart implementation was restricted to cases where the denominator could be completely factored into linear factors over the rationals. In this paper, we present LinApart2 , an extension of the Laurent series method that removes this factorization requirement. Our new algorithm performs partial fraction decomposition over irreducible polynomial factors of arbitrary degree, avoiding the introduction of algebraic or complex roots. This is achieved through an application of Galois theory and polynomial reduction techniques, allowing us to express expansion coefficients directly in terms of the polynomial coefficients rather than in terms of polynomial roots. The key innovation of LinApart2 lies in its ability to maintain the performance advantages of the Laurent series method while working with unfactored denominators. Our improved algorithm achieves significant speedups compared to traditional methods. Furthermore, the algorithm retains the inherent parallelizability of the Laurent series approach, enabling efficient utilization of modern multi-core architectures. However, we acknowledge that in some special cases, presented in Section 5 , the usage of the Euclidean method or the equation system method proves to be advantageous. Thus, we also include these methods as options in our package. We provide an open-source implementation of LinApart2 in the Wolfram Mathematica language, designed as a high-performance replacement for the built-in Apart command. Benchmarks representing various classes of rational functions demonstrate speedups of several orders of magnitude, with the performance gap widening as the complexity of the problem increases. These improvements enable computations of partial fraction decompositions that were previously intractable due to time or memory constraints. The remainder of this paper is organized as follows. In Section 2 we define the problem and give an overview of possible algorithms. This section also recaps the Laurent series method for linear denominator polynomials used in LinApart . Section 3 explains the classical method using the extended Euclidean algorithm for denominator polynomials of higher degree. This section ends with a non-trivial, fully worked example. In Section 4 , we introduce the Galois method. Applying it to the example of Section 3 highlights that the Galois method is conceptually very different from the method using the Euclidean algorithm. In Section 5 , we present comprehensive benchmarks comparing LinApart2 against the built-in Apart command and our implementation of the Euclidean algorithm across various classes of rational functions. Finally, Section 6 offers conclusions and discusses future extensions of this work. 2 Algorithms for partial fraction decomposition We consider a rational function in the variable x , 1 1 1 Here and in the following we will denote the decomposition variable by x . \displaystyle f(x)=\frac{N(x)}{P(x)}\,, (1) where N(x) and P(x) are polynomials of degrees \deg N and \deg P , respectively. By linearity, we can assume that N(x)=x^{k} is a power of x although (depending on the implementation) it can be more efficient to keep the numerator intact. 2.1 Factorization over the complex numbers Partial fraction decomposition over the complex numbers {\mathbb{C}} requires factorizing P(x) into linear factors, P(x)=\prod_{i\in I}(x-a_{i})^{m_{i}} for some index set I . 2 2 2 Note that a factorization of the denominator into linear factors is beneficial in applications related to symbolic integration in terms of multiple polylogarithms. The partial fraction decomposition takes the form \displaystyle f(x)=F(x)+\sum_{i\in I}\left(\frac{c_{i,1}}{x-a_{i}}+\frac{c_{i,2}}{(x-a_{i})^{2}}+\cdots+\frac{c_{i,m_{i}}}{(x-a_{i})^{m_{i}}}\right)\,, (2) where F(x)\in{\mathbb{C}}[x] is the polynomial that corresponds to the expansion at infinity. This polynomial is determined by a Laurent expansion in y=1/x at y=0 to order \mathcal{O}(y^{0}) . Analogously, we determine the coefficients c_{i,j}\in{\mathbb{C}} by expansion at a_{i} , \displaystyle c_{i,j}=\frac{1}{(m_{i}-j)!}\lim_{x\to a_{i}}\frac{d^{m_{i}-j}}{dx^{m_{i}-j}}\Big((x-a_{i})^{m_{i}}f(x)\Big)\,. (3) This formula is straightforward to implement in

Read the complete text