Straight-line programs in geometric elimination theory

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

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

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

Symbolic computation and algebraic computation (68W30) Numerical computation of solutions to systems of equations (65H10) Computational aspects of higher-dimensional varieties (14Q15)

Related Items

A softly optimal Monte Carlo algorithm for solving bivariate polynomial systems over the integers, Complexity results for triangular sets, Discovering the Roots: Uniform Closure Results for Algebraic Classes Under Factoring, A probabilistic algorithm for computing data-discriminants of likelihood equations, Lower bounds for diophantine approximations, Bounds for the Hilbert function of polynomial ideals and for the degrees in the Nullstellensatz, Generalized polar varieties: geometry and algorithms, Numeric vs. symbolic homotopy algorithms in polynomial system solving: a case study, Computing generators of the ideal of a smooth affine algebraic variety, Polar varieties, real equation solving, and data structures: the hypersurface case, Modular equations for hyperelliptic curves, Certifying solutions to overdetermined and singular polynomial systems over \(\mathbb{Q}\), On the complexity exponent of polynomial system solving, Polynomial equation solving by lifting procedures for ramified fibers, Deformation techniques to solve generalised Pham systems, Modular composition modulo triangular sets and applications, Positive dimensional parametric polynomial systems, connectivity queries and applications in robotics, Multistationarity in structured reaction networks, Effective differential Lüroth's theorem, p-adic algorithm for bivariate Gröbner bases, Sparse resultants and straight-line programs, Bit complexity for multi-homogeneous polynomial system solving -- application to polynomial minimization, Foveal detection and approximation for singularities., Computing isolated roots of sparse polynomial systems in affine space, A concise proof of the Kronecker polynomial system solver from scratch, Computing the characteristic polynomial of multivariate polynomial matrices given by straight-line programs, Further perspectives on elimination, A baby steps/giant steps probabilistic algorithm for computing roadmaps in smooth bounded real hypersurface, Algorithms of intrinsic complexity for point searching in compact real singular hypersurfaces, Weak identifiability for differential algebraic systems, Effective coefficient asymptotics of multivariate rational functions via semi-numerical algorithms for polynomial systems, Computing the equidimensional decomposition of an algebraic closed set by means of lifting fibers, Bezoutian and quotient ring structure, On the probability distribution of singular varieties of given corank, Computing multihomogeneous resultants using straight-line programs, Solving determinantal systems using homotopy techniques, On the bit complexity of polynomial system solving, Time-space tradeoffs in algebraic complexity theory, Deformation techniques for efficient polynomial equation solving., Homotopy techniques for solving sparse column support determinantal polynomial systems, Change of order for regular chains in positive dimension, Intrinsic complexity estimates in polynomial optimization, Irreducible decomposition of curves, A Gröbner free alternative for polynomial system solving, Kronecker's and Newton's approaches to solving: a first comparison, On sign conditions over real multivariate polynomials, A parametric representation of totally mixed Nash equilibria, Computing bases of complete intersection rings in Noether position, Practical and Theoretical Issues for the Computation of Generalized Critical Values of a Polynomial Mapping, Properness defects of projection and minimal discriminant variety, Evaluation properties of invariant polynomials, An algorithm for implicit interpolation, EVALUATION PROPERTIES OF SYMMETRIC POLYNOMIALS, Interpolation of polynomials given by straight-line programs, Deformation techniques for sparse systems, Unnamed Item, A sparse effective Nullstellensatz, An effective algorithm for quantifier elimination over algebraically closed fields using straight line programs, Fast computation of a rational point of a variety over a finite field, Functional programming concepts and straight-line programs in computer algebra, Degeneracy loci and polynomial equation solving, Bit complexity for computing one point in each connected component of a smooth real algebraic set, Computing critical points for invariant algebraic systems, Effective equidimensional decomposition of affine varieties, Point searching in real singularcomplete intersection varieties: algorithms of intrinsic complexity, Enumerating a subset of the integer points inside a Minkowski sum, Systems of rational polynomial equations have polynomial size approximate zeros on the average

Cites Work