The Complexity and Parallel Implementation of Two Sparse Multivariate Hensel Lifting Algorithms for Polynomial Factorization

Sparse multivariate Hensel lifting (SHL) algorithms are used in multivariate polynomial factorization as efficient randomized algorithms. They improve on Wang’s classical multivariate Hensel lifting which can be exponential in the number of variables for sparse factors. In this work, we present worst case complexity analyses and failure probability bounds for two recently developed SHL algorithms. One of the algorithms solves the multivariate Diophantine equations using sparse interpolation, and the other interpolates the factors directly from bivariate images obtained using bivariate Hensel lifting. We have observed that a linear expression swell occurs in both approaches. We have modified the second approach to eliminate the expression swell. Our improvement also injects more parallelism into the sparse interpolation step. We have made a high-performance parallel implementation of our new SHL algorithm in Cilk C. We present timing benchmarks comparing our Cilk C implementation with the factorization algorithms in Maple and Magma. We obtain good parallel speedup and our algorithm is much faster than Maple and Magma on our benchmarks.