Complexity of Bezout’s Theorem IV: Probability of Success; Extensions

DOI10.1137/0733008zbMath0843.65035OpenAlexW1965654736MaRDI QIDQ4875494

Publication date: 15 August 1996

Published in: SIAM Journal on Numerical Analysis (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/5ddb95ebb309d4ab69ceea9217e9b3574a8db51e

zbMATH Keywords

complexity condition number unitary group path following integral geometry homotopy methods system of polynomial equations Bezout's theorem projective Newton method

Mathematics Subject Classification ID

Numerical computation of solutions to systems of equations (65H10) Global methods, including homotopy approaches to the numerical solution of nonlinear equations (65H20) Zeros of polynomials, rational functions, and other analytic functions of one complex variable (e.g., zeros of functions with bounded Dirichlet integral) (30C15) General theory of numerical methods in complex analysis (potential theory, etc.) (65E05) Complexity and performance of numerical algorithms (65Y20)

Related Items

Extended Newton methods for conic inequalities: approximate solutions and the extended Smale \(\alpha\)-theory, On generalized Newton algorithms: Quadratic convergence, path-following and error analysis, Complexity of Bezout's theorem. V: Polynomial time, On semilocal convergence analysis for two-step Newton method under generalized Lipschitz conditions in Banach spaces, Newton's Method for Underdetermined Systems of Equations Under the γ-Condition, On the zeta Mahler measure function of the Jacobian determinant, condition numbers and the height of the generic discriminant, Central limit theorem for the volume of the zero set of Kostlan-Shub-Smale random polynomial systems, Lower bounds for diophantine approximations, Symplectic methods for the approximation of the exponential map and the Newton iteration on Riemannian submanifolds, Polar varieties, real equation solving, and data structures: the hypersurface case, Smoothed analysis of complex conic condition numbers, Condition operators, condition numbers, and condition number theorem for the generalized eigenvalue problem, Improved two-step Newton's method for computing simple multiple zeros of polynomial systems, High probability analysis of the condition number of sparse polynomial systems, Deformation techniques to solve generalised Pham systems, Optimal and nearly optimal algorithms for approximating polynomial zeros, On the geometry and topology of the solution variety for polynomial system solving, A deterministic algorithm to compute approximate roots of polynomial systems in polynomial average time, Condition of Intersecting a Projective Variety with a Varying Linear Subspace, Smale's fundamental theorem of algebra reconsidered, Complexity of path-following methods for the eigenvalue problem, Sampling and homology via bottlenecks, A continuation method to solve polynomial systems and its complexity, Rigid continuation paths II. structured polynomial systems, Fast linear homotopy to find approximate zeros of polynomial systems, Condition number based complexity estimate for solving polynomial systems, Spherical Radon transform and the average of the condition number on certain Schubert subvarieties of a Grassmannian, Computational complexity of kernel-based density-ratio estimation: a condition number analysis, Geometry of polynomials and root-finding via path-lifting, Extending the applicability of the Gauss-Newton method under average Lipschitz-type conditions, On the expected number of zeros of nonlinear equations, An arithmetic Poisson formula for the multi-variate resultant, A comparison of eigenvalue condition numbers for matrix polynomials, A numerical algorithm for zero counting. III: Randomization and condition, Globally convergent, iterative path-following for algebraic equations, Complexity of sparse polynomial solving: homotopy on toric varieties and the condition metric, On a problem posed by Steve Smale, Kantorovich's type theorems for systems of equations with constant rank derivatives, On the probability distribution of singular varieties of given corank, Deformation techniques for efficient polynomial equation solving., Approximating complex polynomial zeros: modified Weyl's quadtree construction and improved Newton's iteration., Computing the homology of real projective sets, The unavoidable condition\dots A report on the book. Book review of: P. Bürgisser and F. Cucker, Condition. The geometry of numerical algorithms, Local convergence analysis of inexact Gauss-Newton method for singular systems of equations under majorant and center-majorant condition, Fast computation of zeros of polynomial systems with bounded degree under finite-precision, On the probability distribution of data at points in real complete intersection varieties, Foreword. What is numerical algebraic geometry?, A numerical algorithm for zero counting. I: Complexity and accuracy, Grid methods in computational real algebraic (and semialgebraic) geometry, The probability that a slightly perturbed numerical analysis problem is difficult, Numerical computation of the genus of an irreducible curve within an algebraic set, Stochastic perturbations and smooth condition numbers, On the solution of systems of equations with constant rank derivatives, A THEORY OF COMPLEXITY, CONDITION, AND ROUNDOFF, Kronecker's and Newton's approaches to solving: a first comparison, Structured total least squares approach for efficient frequency estimation, Convergence behavior of Gauss-Newton's method and extensions of the Smale point estimate theory, On the geometry of Graeffe iteration, On a condition number of general random polynomial systems, Quantitative Analysis for Perturbed Abstract Inequality Systems in Banach Spaces, Multihomogeneous Newton methods, Newton's method for overdetermined systems of equations, On isolation of simple multiple zeros and clusters of zeros of polynomial systems, Computing the homology of semialgebraic sets. I: Lax formulas, Smale’s 17th problem: Average polynomial time to compute affine and projective solutions, Smale 17th Problem: Advances and Open Directions, Computing the homology of semialgebraic sets. II: General formulas, Rigid continuation paths I. Quasilinear average complexity for solving polynomial systems, Complexity of Bezout's theorem. VI: Geodesics in the condition (number) metric, Complexity of Bezout's theorem. VII: Distance estimates in the condition metric, Real lines on random cubic surfaces, Some lower bounds for the complexity of continuation methods, On the probability distribution of condition numbers of complete intersection varieties and the average radius of convergence of Newton's method in the underdetermined case, Perturbation theory for homogeneous polynomial eigenvalue problems, Real computations with fake numbers, Newton's method for analytic systems of equations with constant rank derivatives, Does optimality imply ill-posedness? some remarks about certain min-max optimization problems, Systems of rational polynomial equations have polynomial size approximate zeros on the average, On simple double zeros and badly conditioned zeros of analytic functions of 𝑛 variables