Complexity of Bezout’s Theorem IV: Probability of Success; Extensions
- 1 February 1996
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Numerical Analysis
- Vol. 33 (1) , 128-148
- https://doi.org/10.1137/0733008
Abstract
. We estimate the probability that a given number of projective Newton stepsapplied to a linear homotopy of a system of n homogeneous polynomial equations in n + 1complex variables of fixed degrees will find all the roots of the system. We also extend theframework of our analysis to cover the classical implicit function theorem and revisit thecondition number in this context. Further complexity theory is developed.1. Introduction.1A. Bezout's Theorem Revisited.Let f : Cn+1#Cnbe ...Keywords
This publication has 21 references indexed in Scilit:
- Specified precision polynomial root isolation is in NCJournal of Computer and System Sciences, 1994
- How many eigenvalues of a random matrix are real?Journal of the American Mathematical Society, 1994
- Continuation and path followingActa Numerica, 1993
- On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machinesBulletin of the American Mathematical Society, 1989
- The probability that a numerical analysis problem is difficultMathematics of Computation, 1988
- Sphere Packings, Lattices and GroupsPublished by Springer Nature ,1988
- On condition numbers and the distance to the nearest ill-posed problemNumerische Mathematik, 1987
- Sequential and parallel complexity of approximate evaluation of polynomial zerosComputers & Mathematics with Applications, 1987
- Invariant ManifoldsLecture Notes in Mathematics, 1977
- The approximation of one matrix by another of lower rankPsychometrika, 1936