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