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

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

Authors Alexander Brandt, Marc Moreno Maza 

Publication date 24 March 2022

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

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)

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.

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

Cites work

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

Cited in

(1)

• Hensel construction with an arbitrary degree of convergence

Describes a project that uses

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)