Partial fraction decomposition in \(\mathbb{C}(z)\) and simultaneous Newton iteration for factorization in \(\mathbb{C}^{[z]}\) (Q1273735)

This paper presents fast numerical algorithms for factoring univariate polynomials with complex coefficients and for computing partial decomposition (PFDs) of rational functions in one complex variable. Rigorous proofs for the correctness of the algorithms and for favourable asymptotic time bounds with respect to bit complexity are given. Numerically stable and computationally feasible versions of PFD are specified first for the special case of rational functions with all singularities in the unit disk (the bounded case) and then for rational functions with arbitrarily distributed singularities. Two major algorithms for computing PFDs are presented. The first one is an extension of the splitting method by A. Schönhage (1982). The second algorithm is a Newton iteration for simultaneously improving the accuracy of all factors in an approximate PFD of a rational function. Algorithmically useful starting value conditions for the Newton algorithm are provided. Three subalgorithms are of independent interest. They compute the product of a sequence of polynomials, the sum of a sequence of rational functions, and the modular representation of a polynomial. All algorithms are described in a great detail, and numerous technical auxiliaries are provided which are also useful for the design and analysis of other algorithms in computational complex analysis. Combining the splitting circle method with simultaneous Newton iteration yields favourable time bounds, measured in bit iterations, for PFD, polynomial factoring, and root calculation. In particular, the time bounds for computing high accuracy PFDs, high accuracy factorizations, and high accuracy approximations for zeros of squarefree polynomials are linear in the output size, and hence optimal, up to logarithmic factors.