Parallel methods for absolute irreducibility testing

A heuristic algorithm for testing absolute irreducibility of multivariate polynomials over arbitrary fields using Newton polytopes was proposed in Gao and Lauder (Discrete Comput. Geom. 26:89–104, 2001]). A preliminary implementation by Gao and Lauder (2003) established a wide range of families of low degree and sparse polynomials for which the algorithm works efficiently and with a high success rate. In this paper, we develop a BSP variant of the absolute irreducibility testing via polytopes, with the aim of producing a more memory and run-time efficient method that can provide wider ranges of applicability, specifically in terms of the degrees of the input polynomials. In the bivariate case, we describe a balanced load scheme and a corresponding data distribution leading to a parallel algorithm whose efficiency can be established under reasonably realistic conditions. This is later incorporated in a doubly parallel algorithm in the multivariate case that achieves similar scalable performance. Both parallel models are analyzed for efficiency, and the theoretical analysis is compared to the performance of our experiments. In the empirical results we report, we achieve absolute irreducibility testing for bivariate and trivariate polynomials of degrees up to 30,000, and for low degree multivariate polynomials with more than 3,000 variables. To the best of our knowledge, this sets a world record in establishing absolute irreducibility of multivariate polynomials.