Polynomial-Time Reductions from Multivariate to Bi- and Univariate Integral Polynomial Factorization
From MaRDI portal
Publication:3743372
DOI10.1137/0214035zbMath0605.12001OpenAlexW1980267752MaRDI QIDQ3743372
Publication date: 1985
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/633b0b9ef66b08f18460c6ca494c1a19be4fee15
polynomial factorizationmultivariate polynomialsalgorithm analysisintegral polynomialpolynomial-time complexityHensel lemmaHilbert irreducibility theorem
Symbolic computation and algebraic computation (68W30) Number-theoretic algorithms; complexity (11Y16) Polynomials in real and complex fields: factorization (12D05) Polynomials over finite fields (11T06) Polynomials (irreducibility, etc.) (11R09) Computational methods for problems pertaining to field theory (12-08)
Related Items
Factoring sparse multivariate polynomials, Fast parallel absolute irreducibility testing, Irreducibility of multivariate polynomials, Discovering the Roots: Uniform Closure Results for Algebraic Classes Under Factoring, Factoring multivariate polynomials via partial differential equations, Factors of low individual degree polynomials, Algorithms for near solutions to polynomial equations, Computer algebra: Past and future, Deterministic distinct-degree factorization of polynomials over finite fields, Certifying solutions to overdetermined and singular polynomial systems over \(\mathbb{Q}\), Deformation techniques to solve generalised Pham systems, Factoring bivariate sparse (lacunary) polynomials, An effective description of the roots of bivariates mod pk and the related Igusa’s local zeta function, New Sparse Multivariate Polynomial Factorization Algorithms over Integers, Computation of Darboux polynomials and rational first integrals with bounded degree in polynomial time, A note on Gao's algorithm for polynomial factorization, Unnamed Item, On computing the intersection of a pair of algebraic surfaces, Interpolating polynomials from their values, Computation of étale cohomology on curves in single exponential time, Time-bounded termination analysis for probabilistic programs with delays, Computing with polynomials given by black boxes for their evaluations: greatest common divisors, factorization, separation of numerators and denominators, Sparse bivariate polynomial factorization, Improved dense multivariate polynomial factorization algorithms, Computing the multilinear factors of lacunary polynomials without heights, Computational complexity of sentences over fields, Random arithmetic formulas can be reconstructed efficiently, A pre-test for factoring bivariate polynomials with coefficients in \(\mathbb F_2\), The numerical factorization of polynomials, An efficient sparse adaptation of the polytope method over \(\mathbb F_q\) and a record-high binary bivariate factorisation, Complexity of solving parametric polynomial systems, Rational solutions of Riccati-like partial differential equations, An empirical study of cache-oblivious polygon indecomposability testing, Efficient algorithms for computing rational first integrals and Darboux polynomials of planar polynomial vector fields, Efficient \(q\)-integer linear decomposition of multivariate polynomials, Parallel methods for absolute irreducibility testing, A conflict-driven solving procedure for poly-power constraints, Computing the irreducible real factors and components of an algebraic curve, Deterministic irreducibility testing of polynomials over large finite fields, Sentences over integral domains and their computational complexities, Computing a context-free grammar-generating series, Approximate solutions of polynomial equations., Complexity of factoring and calculating the GCD of linear ordinary differential operators, Heuristics to sift extraneous factors in Dixon resultants
