# Recent Advances in Real Complexity and Computation

Share this page *Edited by *
*José Luis Montaña; Luis M. Pardo*

This volume is composed of six contributions derived from the lectures
given during the UIMP-RSME Lluís Santaló Summer School
on “Recent Advances in Real Complexity and Computation”, held July
16–20, 2012, in Santander, Spain.

The goal of this Summer School was to present some of the recent
advances on Smale's 17th Problem: “Can a zero of \(n\)
complex polynomial equations in \(n\) unknowns be found
approximately, on the average, in polynomial time with a uniform
algorithm?”

These papers cover several aspects of this problem: from numerical
to symbolic methods in polynomial equation solving, computational
complexity aspects (both worse and average cases and both upper and
lower complexity bounds) as well as aspects of the underlying geometry
of the problem. Some of the contributions also deal with either real
or multiple solutions solving.

This book is published in cooperation with Real Sociedad Matemática Española (RSME)

# Table of Contents

## Recent Advances in Real Complexity and Computation

- Editors’ preface ix10 free
- Topics in real and complex number complexity theory 114 free
- Polar, bipolar and copolar varieties: Real solving of algebraic varieties with intrinsic complexity 5568
- The complexity and geometry of numerically solving polynomial systems. 7184
- 1. The modern numerical approach to polynomial system solving 7184
- 2. A technical description of the problem 7285
- 3. Geometry and condition number 7588
- 4. The complexity of following a homotopy path 7790
- 5. The problem of good starting points 7891
- 6. The condition Lipschitz–Riemannian structure 8497
- 7. Condition geodesics and the geometry of \CW 87100
- 8. The univariate case and elliptic Fekete points 89102
- 9. The algebraic eigenvalue problem 92105
- Appendix A. A model of computation for machines with round-off and input errors 93106
- References 101114

- Multiplicity hunting and approximating multiple roots of polynomial systems 105118
- 1. Introduction 105118
- 2. Multiplicity. Algebraic geometric point of view 108121
- 3. Multiplicity. Numerical point of view 111124
- 4. Multiplicity and homotopy methods 113126
- 5. Recovering the quadratic convergence 114127
- 6. Deflating and kerneling 117130
- 7. Examples 120133
- 8. Conclusion and future work 124137
- References 125138

- On the intrinsic complexity of elimination problems in effective algebraic geometry 129142
- 1. Introduction 129142
- 2. Concepts and tools from algebraic geometry 130143
- 3. Robust parameterized arithmetic circuits 133146
- 4. A family of hard elimination polynomials 135148
- 5. A computation model with robust parameterized arithmetic circuits 140153
- 6. Applications to elimination theory 145158
- References 147160

- Newton iteration, conditioning and zero counting 151164
- Part 1. Newton Iteration and Alpha theory 153166
- Part 2. Inclusion and exclusion 170183
- Part 3. The algorithm and its complexity 177190