We present a new parallel algorithm for performing linear Hensel lifting of bivariate polynomials over a finite field. The sequential version of our algorithm has a running time of O(m n^4) for lifting m univariate polynomials of degree n with respect to a bivariate polynomial of degree n in both variables, assuming that we use classical polynomial multiplication.
Our parallel algorithm further reduces this complexity
to O(m n/s n^3) on s processing nodes,
assuming that s
We also present an asymptotically faster algorithm, which
has a complexity of O((ln m) n^2 ln n) operations in the
coefficient field, using fast polynomial multiplication
and O(n ln m) processors.
Experimental results on a massively parallel, distributed
memory machine confirm that our algorithm scales well on
high numbers of processing nodes.