On the complexity and parallel implementation of Hensel's lemma and Weierstrass preparation (Q831966)

Assume that \(f\) is a uni-variate polynomial in terms of the variable \(Y\) with multivariate power series coefficients in terms of \(X_1,\ldots ,X_n\). The aim of the Hensel factorization lemma is to provide a method to factor \(f\). In the particular case when \(n=1\), the well-known Newton-Puiseux method computes the roots of \(f\). It is worth noting that Hensel-Sasaki construction is also an alternative method to the Newton-Puiseux method. In this paper, the authors present a parallel algorithm and its implementation for Hensel factorization method based on repeated applications of Weierstrass preparation theorem. Moreover, they give a complexity analysis for this algorithm, leading to the load-balancing of a parallel implementation to concurrently update all factors. Experimental results show the efficacy of proposed method. For the entire collection see [Zbl 1482.68009].