On the complexity and parallel implementation of Hensel's lemma and Weierstrass preparation

DOI10.1007/978-3-030-85165-1_6zbMATH Open1506.13001arXiv2105.10798OpenAlexW3197461373MaRDI QIDQ831966FDOQ831966

Authors: Alexander Brandt, Marc Moreno Maza 

Publication date: 24 March 2022

Abstract: Hensel's lemma, combined with repeated applications of Weierstrass preparation theorem, allows for the factorization of polynomials with multivariate power series coefficients. We present a complexity analysis for this method and leverage those results to guide the load-balancing of a parallel implementation to concurrently update all factors. In particular, the factorization creates a pipeline where the terms of degree k of the first factor are computed simultaneously with the terms of degree k-1 of the second factor, etc. An implementation challenge is the inherent irregularity of computational work between factors, as our complexity analysis reveals. Additional resource utilization and load-balancing is achieved through the parallelization of Weierstrass preparation. Experimental results show the efficacy of this mixed parallel scheme, achieving up to 9x parallel speedup on 12 cores.

Full work available at URL: https://arxiv.org/abs/2105.10798

Recommendations

• Sparse multivariate Hensel lifting: a high-performance design and implementation
• scientific article; zbMATH DE number 1262433
• Parallel and cache-efficient Hensel lifting
• The complexity and parallel implementation of two sparse multivariate Hensel lifting algorithms for polynomial factorization
• scientific article; zbMATH DE number 1263358

zbMATH Keywords

formal power seriesparallel processingHensel's lemmaWeierstrass preparationHensel factorizationparallel pipeline

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Formal power series rings (13F25) Software, source code, etc. for problems pertaining to commutative algebra (13-04)

Cites Work

• Relax, but don't be too lazy
• Title not available (Why is that?)
• Plane algebraic curves. Transl. from the German by Leslie Kay
• On expansion of algebraic functions in power and Puiseux series. I
• All Algebraic Functions Can Be Computed Fast
• Solving multivariate algebraic equation by Hensel construction
• Faster relaxed multiplication
• Parallel direct methods for solving the system of linear equations with pipelining on a multicore using OpenMP
• Infinite structures in Scratchpad II
• Title not available (Why is that?)
• Power series arithmetic with the BPAS library
• On the extended Hensel construction and its application to the computation of real limit points
• Polynomial root finding over local rings and application to error correcting codes
• Enhancing the Extended Hensel Construction by Using Gröbner Bases
• Lazy and Forgetful Polynomial Arithmetic and Applications
• Fast computation of the roots of polynomials over the ring of power series
• On the parallelization of triangular decompositions

Cited In (1)

• Hensel construction with an arbitrary degree of convergence

Uses Software

• gmp
• IBM Scratchpad
• Maple
• NTL
• SageMath
• MultivariatePowerSeries

This page was built for publication: On the complexity and parallel implementation of Hensel's lemma and Weierstrass preparation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q831966)