On the complexity of path-following newton algorithms for solving systems of polynomial equations with integer coefficients
Gregorio Malajovich-Munoz, Steve Smale · 1993
Contents Chapter I. Introduction 1 1. Systems of polynomials with Integer coefficients 1 2. Global complexity of polynomial-solving 2 3. The geometry of polynomial-solving 4 4. Outline of this Thesis. 5 5. Acknowledgements 6 Chapter II. On generalized Newton algorithms ... 8 1. Introduction 8 2. Estimates on fi 16 3. Estimates on fl 19 4. Estimates on ff 20 5. Estimates on 24 6. Proof of the Robustness results 26 Chapter III. Construction of the Approximate Newton Operator 31 1. Introduction 31 2. Basic definitions 35 iii iv 3. Algorithms 38 4. Sketch of the proof of Theorems 11 and 12 40 5. Forward error analysis of Phase 1 41 6. Some backward error analysis identities 42 7. Backward error analysis of Phase 2 45 8. Conditioning of M 46 9. First order analysis 49 10. Construction of the finite precision machine 50 11. Polynomial time analysis 52 Chapter IV. Gap theory and estim