approximate factorization of polynomials over z
We propose three algorithms for approximate factorization of univariate polynomials over Z ; the first one uses sums of powers of roots (SPR method), the second one utilizes factor-differentiated polynomials (FD method), and the third one is a robust but slow method. The SPR method is applicable to monic polynomials well but it is almost useless for non-monic polynomials unless their leading coefficients are sufficiently small. The FD method is applicable to both monic and non-monic polynomials, but it also becomes useless if both the leading and the tail coefficients increase. The third one is applicable to any polynomial factorizable approximately over Z , but it is slow. We discuss two types of polynomials which are ill-conditioned for rootfinding, Wilkinson-type polynomials and polynomials with close roots. Furthermore, we consider briefly approximate factorization of multivariate polynomials over Z .
sum of powers of roots factor-differentiated polynomials knapsack method approximate factorization over z