Complexity of Bezout's Theorem I: Geometric Aspects

DOI10.2307/2152805zbMath0821.65035OpenAlexW4231932295WikidataQ56697971 ScholiaQ56697971MaRDI QIDQ4039362

Michael Shub, Stephen Smale

Publication date: 27 September 1995

Published in: Journal of the American Mathematical Society (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.2307/2152805

zbMATH Keywords

complexityconvergenceNewton's methodsystems of polynomial equationsill-posed problemshomotopy methodsBezout's theorem

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) Real polynomials: location of zeros (26C10)

Related Items (only showing first 100 items - show all)

Certification for polynomial systems via square subsystems ⋮ Complexity of Bezout's theorem. V: Polynomial time ⋮ 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 ⋮ A universal constant for the convergence of Newton's method and an application to the classical homotopy method ⋮ A primal-dual formulation for certifiable computations in Schubert calculus ⋮ 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 ⋮ Perturbation results on the zero-locus of a polynomial ⋮ Smoothed analysis of complex conic condition numbers ⋮ Mixed discriminants ⋮ A property of the nearly optimal root-bound ⋮ On the condition of the zeros of characteristic polynomials ⋮ High probability analysis of the condition number of sparse polynomial systems ⋮ Deformation techniques to solve generalised Pham systems ⋮ Polynomial root finding by means of continuation ⋮ Optimal and nearly optimal algorithms for approximating polynomial zeros ⋮ Mixed-volume computation by dynamic lifting applied to polynomial system solving ⋮ Linear programming, complexity theory and elementary functional analysis ⋮ Computations in the neighbourhood of algebraic singularities ⋮ 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 ⋮ Smale's fundamental theorem of algebra reconsidered ⋮ Complexity of path-following methods for the eigenvalue problem ⋮ A continuation method to solve polynomial systems and its complexity ⋮ Certified predictor-corrector tracking for Newton homotopies ⋮ Fast linear homotopy to find approximate zeros of polynomial systems ⋮ Spherical Radon transform and the average of the condition number on certain Schubert subvarieties of a Grassmannian ⋮ A universality property of Gaussian analytic functions ⋮ Geometry of polynomials and root-finding via path-lifting ⋮ Low-degree approximation of random polynomials ⋮ A subdivision method for computing nearest gcd with certification ⋮ A fast Chebyshev's method for quadratic equations. ⋮ Robust certified numerical homotopy tracking ⋮ On the expected number of zeros of nonlinear equations ⋮ An arithmetic Poisson formula for the multi-variate resultant ⋮ A complex analogue of Toda's theorem ⋮ General equilibrium models and homotopy methods ⋮ A numerical algorithm for zero counting. III: Randomization and condition ⋮ Local convergence of some iterative methods for generalized equations. ⋮ Globally convergent, iterative path-following for algebraic equations ⋮ Complexity of sparse polynomial solving: homotopy on toric varieties and the condition metric ⋮ Probabilistic condition number estimates for real polynomial systems. I: A broader family of distributions ⋮ Convergence criterion of Newton's method for singular systems with constant rank derivatives ⋮ On a problem posed by Steve Smale ⋮ On the probability distribution of singular varieties of given corank ⋮ Finding zeros of analytic functions: \(\alpha\)-theory for secant type methods ⋮ Complexity analysis for certain convex programming problems ⋮ Solving determinantal systems using homotopy techniques ⋮ High order iterative schemes for quadratic equations ⋮ 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 ⋮ A few problems on monodromy and discriminants ⋮ Minimizing the discrete logarithmic energy on the sphere: The role of random polynomials ⋮ The unavoidable condition\dots A report on the book. Book review of: P. Bürgisser and F. Cucker, Condition. The geometry of numerical algorithms ⋮ On the probability distribution of data at points in real complete intersection varieties ⋮ Condition length and complexity for the solution of polynomial systems ⋮ Foreword. What is numerical algebraic geometry? ⋮ Certifying solutions to square systems of polynomial-exponential equations ⋮ A numerical algorithm for zero counting. I: Complexity and accuracy ⋮ Grid methods in computational real algebraic (and semialgebraic) geometry ⋮ Local convergence of Newton-like methods for generalized equations ⋮ The probability that a slightly perturbed numerical analysis problem is difficult ⋮ On continued fraction expansion of real roots of polynomial systems, complexity and condition numbers ⋮ Numerical computation of the genus of an irreducible curve within an algebraic set ⋮ An adaptive version of a fourth-order iterative method for quadratic equations ⋮ A note on the finite variance of the averaging function for polynomial system solving ⋮ Galois groups of Schubert problems via homotopy computation ⋮ On a condition number of general random polynomial systems ⋮ On the geometry of the set of symmetric matrices with repeated eigenvalues ⋮ Extending the applicability of Newton's method on Lie groups ⋮ Computing the homology of semialgebraic sets. I: Lax formulas ⋮ On the Solvability Complexity Index, the 𝑛-pseudospectrum and approximations of spectra of operators ⋮ Smale’s 17th problem: Average polynomial time to compute affine and projective solutions ⋮ Smale 17th Problem: Advances and Open Directions ⋮ Complexity of Bezout's theorem. VI: Geodesics in the condition (number) metric ⋮ Complexity of Bezout's theorem. VII: Distance estimates in the condition metric ⋮ The real polynomial eigenvalue problem is well conditioned on the average ⋮ Partial fraction decomposition in \(\mathbb{C}(z)\) and simultaneous Newton iteration for factorization in \(\mathbb{C}^{[z}\)] ⋮ Random fields and the enumerative geometry of lines on real and complex hypersurfaces ⋮ Some lower bounds for the complexity of continuation methods ⋮ Counting problems over the reals ⋮ The constrained Newton method on a Lie group and the symmetric eigenvalue problem ⋮ The Polynomial Eigenvalue Problem is Well Conditioned for Random Inputs ⋮ Adaptive strategies for solving parameterized systems using homotopy continuation ⋮ A facility location formulation for stable polynomials and elliptic Fekete points ⋮ A randomized homotopy for the Hermitian eigenpair problem ⋮ 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 ⋮ Exact solutions in log-concave maximum likelihood estimation ⋮ Real computations with fake numbers ⋮ Newton's method for analytic systems of equations with constant rank derivatives ⋮ Kantorovich's theorem on Newton's method in Riemannian manifolds ⋮ Distributing many points on spheres: minimal energy and designs ⋮ Mysteries of mathematics and computation ⋮ 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 ⋮ A condition number theorem for underdetermined polynomial systems

This page was built for publication: Complexity of Bezout's Theorem I: Geometric Aspects