Straight-line programs in geometric elimination theory

DOI10.1016/S0022-4049(96)00099-0zbMath0944.12004arXivalg-geom/9609005MaRDI QIDQ1380007

Joos Heintz, Marc Giusti, Luis Miguel Pardo, Jacques Morgenstern, J. E. Morais

Publication date: 29 May 2000

Published in: Journal of Pure and Applied Algebra (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/alg-geom/9609005

zbMATH Keywords

complexity; geometric degree; elimination; polynomial system solving; arithmetic networks; encoding polynomials by straight-line programs; greatest common divisor of univariate polynomials; primitive element constructions; shape lemmas

Mathematics Subject Classification ID

68W30: Symbolic computation and algebraic computation

65H10: Numerical computation of solutions to systems of equations

14Q15: Computational aspects of higher-dimensional varieties

Related Items

Modular equations for hyperelliptic curves, EVALUATION PROPERTIES OF SYMMETRIC POLYNOMIALS, A Gröbner free alternative for polynomial system solving, Kronecker's and Newton's approaches to solving: a first comparison, Computing bases of complete intersection rings in Noether position, Polynomial equation solving by lifting procedures for ramified fibers, Deformation techniques to solve generalised Pham systems, Irreducible decomposition of curves, Evaluation properties of invariant polynomials, On sign conditions over real multivariate polynomials, A parametric representation of totally mixed Nash equilibria, Interpolation of polynomials given by straight-line programs, Deformation techniques for sparse systems, A sparse effective Nullstellensatz, An effective algorithm for quantifier elimination over algebraically closed fields using straight line programs, Lower bounds for diophantine approximations, Bounds for the Hilbert function of polynomial ideals and for the degrees in the Nullstellensatz, Polar varieties, real equation solving, and data structures: the hypersurface case, Foveal detection and approximation for singularities., Computing the characteristic polynomial of multivariate polynomial matrices given by straight-line programs, Effective equidimensional decomposition of affine varieties, Enumerating a subset of the integer points inside a Minkowski sum, Functional programming concepts and straight-line programs in computer algebra, Systems of rational polynomial equations have polynomial size approximate zeros on the average, Complexity results for triangular sets, Time-space tradeoffs in algebraic complexity theory, Deformation techniques for efficient polynomial equation solving., Generalized polar varieties: geometry and algorithms, Numeric vs. symbolic homotopy algorithms in polynomial system solving: a case study, A concise proof of the Kronecker polynomial system solver from scratch, Bezoutian and quotient ring structure, On the probability distribution of singular varieties of given corank, Computing multihomogeneous resultants using straight-line programs, Change of order for regular chains in positive dimension, Computing generators of the ideal of a smooth affine algebraic variety, Fast computation of a rational point of a variety over a finite field, Practical and Theoretical Issues for the Computation of Generalized Critical Values of a Polynomial Mapping

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On computing the determinant in small parallel time using a small number of processors
• Definability and fast quantifier elimination in algebraically closed fields
• On the Sprindžuk-Weissauer approach to universal Hilbert subsets
• Bounds for the degrees in the Nullstellensatz
• Hilbert irreducibility sequences and nonstandard arithmetic
• Résolution des systèmes d'équations algébriques
• Factoring polynomials with rational coefficients
• The complexity of partial derivatives
• The membership problem for unmixed polynomial ideals is solvable in single exponential time
• On the irreducibility of the polynomials \(P(t^ m,Y)\)
• A probabilistic remark on algebraic program testing
• On the intrinsic complexity of elimination theory
• Complexity of Bezout's theorem. V: Polynomial time
• Polynomial-time computation of the dimensions of components of algebraic varieties in zero-characteristic
• Lower bounds for arithmetic networks
• Bounds of traces in complete intersections and degrees in the Nullstellensatz
• Dynamic evaluation and algebraic closure in Axiom
• On the efficiency of effective Nullstellensätze
• A combinatorial proof of the effective Nullstellensatz
• Generic local structure of the morphisms in commutative algebra
• Die Berechnungskomplexität von elementarsymmetrischen Funktionen und von Interpolationskoeffizienten
• Effective Bezout identities in \({\mathbb{Q}}[z_ 1,\dots ,z_ n\)]
• Greatest common divisors of polynomials given by straight-line programs
• Dénominateurs dans le théorème des zéros de Hilbert
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• Probabilistic Algorithms for Deciding Equivalence of Straight-Line Programs
• Une formule de Jacobi et ses conséquences
• Sharp Effective Nullstellensatz