Fast computation of contour integrals of rational functions (Q1977145)

If polynomials \(q, p\in \mathbb{C}[z]\) and a complex curve \(\Gamma\) are given, the contour integral \(\int_\Gamma q(z)/p(z)dz\) is computed up to a prescribed error. The first step of this fast algorithm is a decomposition of \(q/p\) into partial fractions corresponding to well separated clusters of roots of \(p\), where the author's method [J. Complexity 14, No. 3, 378-444 (1998; Zbl 0934.12005)] is used. Then the integrals of the partial fractions are computed by integrating their Laurent series termwise. This algorithm is analyzed with respect to the bit complexity. The running time of the algorithm is also estimated.