zbMATH — the first resource for mathematics

Sparse multivariate Hensel lifting: a high-performance design and implementation. (English) Zbl 1395.68349
Davenport, James H. (ed.) et al., Mathematical software – ICMS 2018. 6th international conference, South Bend, IN, USA, July 24–27, 2018. Proceedings. Cham: Springer (ISBN 978-3-319-96417-1/pbk; 978-3-319-96418-8/ebook). Lecture Notes in Computer Science 10931, 359-368 (2018).
Summary: Our goal is to develop a high-performance code for factoring a multivariate polynomial in \(n\) variables with integer coefficients which is polynomial time in the sparse case and efficient in the dense case. Maple, Magma, Macsyma, Singular and Mathematica all implement Wang’s multivariate Hensel lifting, which, for sparse polynomials, can be exponential in \(n\). Wang’s algorithm is also highly sequential.
In this work we reorganize multivariate Hensel lifting to facilitate a high-performance parallel implementation. We identify multivariate polynomial evaluation and bivariate Hensel lifting as two core components. We have also developed a library of algorithms for polynomial arithmetic which allow us to assign each core an independent task with all the memory it needs in advance so that memory management is eliminated and all important operations operate on dense arrays of 64 bit integers. We have implemented our algorithm and library using Cilk C for the case of two monic factors. We discuss details of the implementation and present experimental timing results.
For the entire collection see [Zbl 1391.68004].

68W30 Symbolic computation and algebraic computation
13P05 Polynomials, factorization in commutative rings
Full Text: DOI