Complexity of Bezout's theorem IV: Probability of success; extensions

Michael Shub; Steve Smale

Complexity of Bezout's theorem IV: Probability of success; extensions

Michael Shub
, Steve Smale

Department of Mathematics

Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review

116 Citations (Scopus)

Abstract

We estimate the probability that a given number of projective Newton steps applied to a linear homotopy of a system of n homogeneous polynomial equations in n + 1 complex variables of fixed degrees will find all the roots of the system. We also extend the framework of our analysis to cover the classical implicit function theorem and revisit the condition number in this context. Further complexity theory is developed.

© 1996 Society for Industrial and Applied Mathematics

Original language	English
Pages (from-to)	128-148
Journal	SIAM Journal on Numerical Analysis
Volume	33
Issue number	1
Publication status	Published - Feb 1996

Research Keywords

Bezout's theorem
Complexity
Homotopy methods
Integral geometry
Path following
Unitary group

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

@article{1276c475422e44c6b7d8bc36f6822a56,

title = "Complexity of Bezout's theorem IV: Probability of success; extensions",

abstract = "We estimate the probability that a given number of projective Newton steps applied to a linear homotopy of a system of n homogeneous polynomial equations in n + 1 complex variables of fixed degrees will find all the roots of the system. We also extend the framework of our analysis to cover the classical implicit function theorem and revisit the condition number in this context. Further complexity theory is developed. {\textcopyright} 1996 Society for Industrial and Applied Mathematics",

keywords = "Bezout's theorem, Complexity, Homotopy methods, Integral geometry, Path following, Unitary group",

author = "Michael Shub and Steve Smale",

year = "1996",

month = feb,

language = "English",

volume = "33",

pages = "128--148",

journal = "SIAM Journal on Numerical Analysis",

issn = "0036-1429",

publisher = "Society for Industrial and Applied Mathematics",

number = "1",

}

TY - JOUR

T1 - Complexity of Bezout's theorem IV

T2 - Probability of success; extensions

AU - Shub, Michael

AU - Smale, Steve

PY - 1996/2

Y1 - 1996/2

N2 - We estimate the probability that a given number of projective Newton steps applied to a linear homotopy of a system of n homogeneous polynomial equations in n + 1 complex variables of fixed degrees will find all the roots of the system. We also extend the framework of our analysis to cover the classical implicit function theorem and revisit the condition number in this context. Further complexity theory is developed. © 1996 Society for Industrial and Applied Mathematics

AB - We estimate the probability that a given number of projective Newton steps applied to a linear homotopy of a system of n homogeneous polynomial equations in n + 1 complex variables of fixed degrees will find all the roots of the system. We also extend the framework of our analysis to cover the classical implicit function theorem and revisit the condition number in this context. Further complexity theory is developed. © 1996 Society for Industrial and Applied Mathematics

KW - Bezout's theorem

KW - Complexity

KW - Homotopy methods

KW - Integral geometry

KW - Path following

KW - Unitary group

UR - https://www.scopus.com/pages/publications/0000675799

UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-0000675799&origin=recordpage

M3 - RGC 21 - Publication in refereed journal

SN - 0036-1429

VL - 33

SP - 128

EP - 148

JO - SIAM Journal on Numerical Analysis

JF - SIAM Journal on Numerical Analysis

IS - 1

ER -

Complexity of Bezout's theorem IV: Probability of success; extensions

Abstract

Research Keywords

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

Cite this