Fast parallel absolute irreducibility testing
From MaRDI portal
Publication:1080657
DOI10.1016/S0747-7171(85)80029-8zbMath0599.68038MaRDI QIDQ1080657
Publication date: 1985
Published in: Journal of Symbolic Computation (Search for Journal in Brave)
finite fieldcomplexity class NCfast parallel deterministic algorithmsequentially polynomial-time problemstesting multivariate integral polynomials for absolute irreducibility
Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30) Polynomials in real and complex fields: factorization (12D05) Polynomials in general fields (irreducibility, etc.) (12E05)
Related Items
Specified precision polynomial root isolation is in NC, Irreducibility of multivariate polynomials, Lifting and recombination techniques for absolute factorization, Comments on Integration of Algebraic Functions, A study of approximate polynomials. I: Representation and arithmetic, Semi-numerical absolute factorization of polynomials with integer coefficients, Deterministic distinct-degree factorization of polynomials over finite fields, Modular Las Vegas algorithms for polynomial absolute factorization, On a generalization of Stickelberger's theorem, Values of polynomials over finite fields, Irreducibility of polynomials modulo \(p\) via Newton polytopes., Computation of Darboux polynomials and rational first integrals with bounded degree in polynomial time, On computing the intersection of a pair of algebraic surfaces, Approximate factorization of multivariate polynomials and absolute irreducibility testing, Improved dense multivariate polynomial factorization algorithms, Computational complexity of sentences over fields, Counting curves and their projections, A unified method for multivariate polynomial factorizations, Approximate factorization of multivariate polynomials using singular value decomposition, Absolute irreducibility of polynomials via Newton polytopes, Rational solutions of Riccati-like partial differential equations, Nearly optimal algorithms for the decomposition of multivariate rational functions and the extended Lüroth theorem, The computational complexity of recognizing permutation functions, The Computational Complexity of the Resolution of Plane Curve Singularities, 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, Control of the non-geometrically integral reductions, Probabilistic absolute irreducibility test for polynomials
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Towards a complexity theory of synchronous parallel computation
- Factoring polynomials with rational coefficients
- Equations over finite fields. An elementary approach
- Parallel computation for well-endowed rings and space-bounded probabilistic machines
- Polynomial-Time Reductions from Multivariate to Bi- and Univariate Integral Polynomial Factorization
- Fast parallel matrix and GCD computations
