Deformation techniques for efficient polynomial equation solving.

DOI10.1006/jcom.1999.0529zbMath1041.65044OpenAlexW2060624832MaRDI QIDQ1977143

Juan Sabia, Joos Heintz, Ariel Waissbein, Susana Puddu, Teresa Krick

Publication date: 2000

Published in: Journal of Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/jcom.1999.0529

zbMATH Keywords

arithmetic circuitNewton-Hensel iterationpolynomial equation systemshape (or primitive element) lemma

Mathematics Subject Classification ID

Numerical computation of solutions to systems of equations (65H10) Computational aspects and applications of commutative rings (13P99)

Related Items

Complexity results for triangular sets, Numeric vs. symbolic homotopy algorithms in polynomial system solving: a case study, Modular equations for hyperelliptic curves, Certifying solutions to overdetermined and singular polynomial systems over \(\mathbb{Q}\), Polynomial equation solving by lifting procedures for ramified fibers, Deformation techniques to solve generalised Pham systems, Sparse resultants and straight-line programs, Computing isolated roots of sparse polynomial systems in affine space, A concise proof of the Kronecker polynomial system solver from scratch, Algorithms of intrinsic complexity for point searching in compact real singular hypersurfaces, A probabilistic symbolic algorithm to find the minimum of a polynomial function on a basic closed semialgebraic set, Computing multihomogeneous resultants using straight-line programs, Solving determinantal systems using homotopy techniques, On the bit complexity of polynomial system solving, Homotopy techniques for solving sparse column support determinantal polynomial systems, Change of order for regular chains in positive dimension, The method of Gauss-Newton to compute power series solutions of polynomial homotopies, Complexity of solving parametric polynomial systems, On sign conditions over real multivariate polynomials, On the complexity of the resolvent representation of some prime differential ideals, On computing absolutely irreducible components of algebraic varieties with parameters, Evaluation properties of invariant polynomials, A linear algebra approach to the differentiation index of generic DAE systems, Puiseux Expansions and Nonisolated Points in Algebraic Varieties, Deformation techniques for sparse systems, Functional programming concepts and straight-line programs in computer algebra, Computing critical points for invariant algebraic systems

Uses Software

• Projective Noether

Cites Work

• On computing the determinant in small parallel time using a small number of processors
• Definability and fast quantifier elimination in algebraically closed fields
• Lectures on results on Bezout's theorem. Notes by D. P. Patil
• Generalised characteristic polynomials
• Solving systems of polynomial inequalities in subexponential time
• On the computational complexity and geometry of the first-order theory of the reals. I: Introduction. Preliminaries. The geometry of semi-algebraic sets. The decision problem for the existential theory of the reals
• Complexity of Bezout's theorem. V: Polynomial time
• Homotopies for solving polynomial systems within a bounded domain
• 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
• On computing a set of points meeting every cell defined by a family of polynomials on a variety
• Straight-line programs in geometric elimination theory
• Bounds of traces in complete intersections and degrees in the Nullstellensatz
• On the affine Bezout inequality
• On the intrinsic complexity of the arithmetic Nullstellensatz
• Complexity of Bezout's theorem. III: Condition number and packing
• Introduction to the theory of analytic spaces
• Generic local structure of the morphisms in commutative algebra
• The Jacobian conjecture: Reduction of degree and formal expansion of the inverse
• Complexity of Bezout's Theorem I: Geometric Aspects
• Le rôle des structures de données dans les problèmes d'élimination
• Sur la complexité du principe de Tarski-Seidenberg
• Complexity of Bezout’s Theorem IV: Probability of Success; Extensions
• 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