Complexity of Bezout's theorem. V: Polynomial time

DOI10.1016/0304-3975(94)90122-8zbMath0846.65022OpenAlexW2063917062MaRDI QIDQ1338222

Publication date: 26 September 1996

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(94)90122-8

zbMATH Keywords

complexity algorithms approximate zero polynomial time system of polynomial equations Bezout's theorem number of arithmetic operations

Mathematics Subject Classification ID

Numerical computation of solutions to systems of equations (65H10) Zeros of polynomials, rational functions, and other analytic functions of one complex variable (e.g., zeros of functions with bounded Dirichlet integral) (30C15) Complexity and performance of numerical algorithms (65Y20)

Related Items (62)

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 ⋮ High probability analysis of the condition number of sparse polynomial systems ⋮ Deformation techniques to solve generalised Pham systems ⋮ Straight-line programs in geometric elimination theory ⋮ Optimal and nearly optimal algorithms for approximating polynomial zeros ⋮ On the geometry and topology of the solution variety for polynomial system solving ⋮ Complexity of path-following methods for the eigenvalue problem ⋮ A continuation method to solve polynomial systems and its complexity ⋮ Rigid continuation paths II. structured polynomial systems ⋮ Certified predictor-corrector tracking for Newton homotopies ⋮ Fast linear homotopy to find approximate zeros of polynomial systems ⋮ Computational complexity of kernel-based density-ratio estimation: a condition number analysis ⋮ Geometry of polynomials and root-finding via path-lifting ⋮ The average condition number of most tensor rank decomposition problems is infinite ⋮ Robust certified numerical homotopy tracking ⋮ On the expected number of zeros of nonlinear equations ⋮ An arithmetic Poisson formula for the multi-variate resultant ⋮ The nearest complex polynomial with a zero in a given complex domain ⋮ 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 ⋮ 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 ⋮ 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 ⋮ Condition length and complexity for the solution of polynomial systems ⋮ Foreword. What is numerical algebraic geometry? ⋮ A fast and stable algorithm for splitting polynomials ⋮ 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 ⋮ On solving univariate sparse polynomials in logarithmic time ⋮ A THEORY OF COMPLEXITY, CONDITION, AND ROUNDOFF ⋮ Kronecker's and Newton's approaches to solving: a first comparison ⋮ A note on the finite variance of the averaging function for polynomial system solving ⋮ On the geometry of Graeffe iteration ⋮ On a condition number of general random polynomial systems ⋮ Multihomogeneous Newton methods ⋮ Newton's method for overdetermined systems of equations ⋮ 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 ⋮ 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 ⋮ Some lower bounds for the complexity of continuation methods ⋮ Computing singular points of projective plane algebraic curves by homotopy continuation methods ⋮ Mathematical problems for the next century ⋮ Numerical continuation methods: a perspective ⋮ 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 ⋮ Real computations with fake numbers ⋮ A numerical realization of the conditions of Max Nöther's residual intersection theorem ⋮ On simple double zeros and badly conditioned zeros of analytic functions of 𝑛 variables

Cites Work

This page was built for publication: Complexity of Bezout's theorem. V: Polynomial time