Kronecker's and Newton's approaches to solving: a first comparison

DOI10.1006/jcom.2000.0572zbMath1013.68296arXivmath/9908082OpenAlexW2155163206MaRDI QIDQ5938585

No author found.

Publication date: 11 August 2002

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

Full work available at URL: https://arxiv.org/abs/math/9908082

zbMATH Keywords

approximate zerodegree of algebraic varietiesheight of diophantine varietiesKronecker's solutionNewton operatorstraight-line programsTuring machine complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30) Nonnumerical algorithms (68W05) Numerical computation of solutions to single equations (65H05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

Generalized polar varieties: geometry and algorithms, Certifying solutions to overdetermined and singular polynomial systems over \(\mathbb{Q}\), Deformation techniques to solve generalised Pham systems, A concise proof of the Kronecker polynomial system solver from scratch, Robust certified numerical homotopy tracking, 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, On the probability distribution of singular varieties of given corank, A probabilistic algorithm to test local algebraic observability in polynomial time, The method of Gauss-Newton to compute power series solutions of polynomial homotopies, Unnamed Item, Numerical analysis of a bisection-exclusion method to find zeros of univariate analytic functions, Systems of rational polynomial equations have polynomial size approximate zeros on the average

Uses Software

• ECPP

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
• 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
• Topological complexity of a root finding algorithm
• Definability and fast quantifier elimination in algebraically closed fields
• Lectures on results on Bezout's theorem. Notes by D. P. Patil
• Sur des hauteurs alternatives. I. (On alternative heights. I)
• Solvability by radicals is in polynomial time
• On the worst-case arithmetic complexity of approximating zeros of polynomials
• Factoring polynomials with rational coefficients
• Exact solution of linear equations using p-adic expansions
• Primality testing and Abelian varieties over finite fields
• Newton polytopes and the Bezout theorem
• Some lower bounds for the complexity of continuation methods
• On generalized Newton algorithms: Quadratic convergence, path-following and error analysis
• Complexity of Bezout's theorem. V: Polynomial time
• Sur des hauteurs alternatives. II (On alternative heights. II)
• Lower bounds for diophantine approximations
• Condition operators, condition numbers, and condition number theorem for the generalized eigenvalue problem
• Straight-line programs in geometric elimination theory
• Estimations for the separation number of a polynomial system
• Lower bounds for arithmetic networks
• A universal constant for the convergence of Newton's method and an application to the classical homotopy method
• Lower bounds for arithmetic networks. II: Sum of Betti numbers
• On alternative heights. III
• On the intrinsic complexity of the arithmetic Nullstellensatz
• Complexity of Bezout's theorem. III: Condition number and packing
• An introduction to the geometry of numbers.
• Computational Complexity: On the Geometry of Polynomials and a Theory of Cost: II
• Elliptic Curves and Primality Proving
• On Approximate Zeros and Rootfinding Algorithms for a Complex Polynomial
• Improving an algorithm for factoring polynomials over a finite field and constructing large irreducible polynomials
• Factoring Polynomials over Algebraic Number Fields
• On the efficiency of algorithms of analysis
• Computational complexity. On the geometry of polynomials and a theory of cost. I
• Polynomial Factorization and Nonrandomness of Bits of Algebraic and Some Transcendental Numbers
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• The fundamental theorem of algebra and complexity theory
• A New Algorithm for Factoring Polynomials Over Finite Fields
• Probabilistic Algorithms for Deciding Equivalence of Straight-Line Programs
• Complexity of Bezout's Theorem I: Geometric Aspects
• Condition Number Analysis for Sparse Polynomial Systems
• Le rôle des structures de données dans les problèmes d'élimination
• On simple double zeros and badly conditioned zeros of analytic functions of 𝑛 variables
• Complexity of Bezout’s Theorem IV: Probability of Success; Extensions
• Newton's method for overdetermined systems of equations