Factoring Multivariate Polynomials Represented by Black Boxes: A Maple + C Implementation

Our goal is to develop fast parallel algorithms to factor multivariate polynomials with integer coefficients. The authors contributed a parallel sparse Hensel lifting algorithm (CMSHL) to factor multivariate polynomials in their sparse representation (Chen and Monagan, in Proceedings of CASC 2020, LNCS 12291, pp 150–169, Springer, Berlin, 2020). The dominating cost of CMSHL is polynomial evaluations. To reduce this cost, in this work we represent the polynomial to be factored by a black box. We give an algorithm that computes the factors of the polynomial in their sparse representation directly using our modified CMSHL algorithm. Our new algorithm requires fewer probes to the black box than the algorithm of Kaltofen and Trager from 1990. We have implemented our algorithm in Maple with major subroutines coded in C. We present timing benchmarks for two examples of factoring determinants of matrices of polynomials. Our algorithm is much faster than Maple’s best determinant and factor algorithms on our benchmarks. We are able to compute the factors of $$\det T_n$$ for $$n=16$$ where $$T_n$$ is the $$n \times n$$ symmetric Toeplitz matrix with symbolic entries $$x_1,x_2,\dots ,x_n$$ .