×

Complexity of Bezout’s theorem. VI: Geodesics in the condition (number) metric. (English) Zbl 1175.65060

Summary: We introduce a new complexity measure of a path of (problems, solutions) pairs in terms of the length of the path in the condition metric which we define in the article. The measure gives an upper bound for the number of Newton steps sufficient to approximate the path discretely starting from one end and thus produce an approximate zero for the endpoint. This motivates the study of short paths or geodesics in the condition metric.
[For part V see M. Shub and S. Smale, Theor. Comput. Sci. 133, No. 1, 141–164 (1994; Zbl 0846.65022).]

MSC:

65H10 Numerical computation of solutions to systems of equations
65H04 Numerical computation of roots of polynomial equations
65H20 Global methods, including homotopy approaches to the numerical solution of nonlinear equations
65Y20 Complexity and performance of numerical algorithms
12Y05 Computational aspects of field theory and polynomials (MSC2010)
30C15 Zeros of polynomials, rational functions, and other analytic functions of one complex variable (e.g., zeros of functions with bounded Dirichlet integral)
PDF BibTeX XML Cite
Full Text: DOI arXiv

References:

[1] C. Beltran and L. M. Pardo, Smale’s 17th problem: A probabilistic positive solution, Found. Comput. Math. 7 (2007), 87–134. · Zbl 1113.15006
[2] C. Beltran and L. M. Pardo, Smale’s 17th problem: Average polynomial time to compute affine and projective solutions. Preprint.
[3] C. Beltran and M. Shub, Complexity of Bezout’s theorem VII: Distance estimates in the condition metric. Found. Comput. Math. (2008). doi: 10.1007/s10208-007-9018-5 . · Zbl 1153.65048
[4] M. Gromov, Metric Structures for Riemannian and Non-Riemannian Spaces, Birkhäuser, Basel, 1998.
[5] L. Blum, F. Cucker, M. Shub, and S. Smale, Complexity and Real Computation, Springer, Berlin, 1998. · Zbl 0872.68036
[6] Y. E. Nesterov and M. J. Todd, On the Riemannian geometry defined by self-concordant barriers and interior-point methods, Found. Comput. Math. 2 (2002), 333–361. · Zbl 1049.90127
[7] M. Shub and S. Smale, Complexity of Bezout’s theorem I: Geometrical aspects, J. Am. Math. Soc. 6 (1993), 459–501. · Zbl 0821.65035
[8] M. Shub and S. Smale, Complexity of Bezout’s theorem II: Volumes and probabilities, in Computational Algebraic Geometry (F. Eyssette and A. Galligo, eds.), Progress in Mathematics, Vol. 109, pp. 267–285, Birkhäuser, Basel, 1993. · Zbl 0851.65031
[9] M. Shub and S. Smale, Complexity of Bezout’s theorem III: Condition number and packing, J. Complex. 9 (1993), 4–14. · Zbl 0846.65018
[10] M. Shub and S. Smale, Complexity of Bezout’s theorem IV: Probability of success; extensions, SINUM 33 (1996), 128–148. · Zbl 0843.65035
[11] M. Shub and S. Smale, Complexity of Bezout’s theorem V: Polynomial time, Theor. Comput. Sci. 133 (1994), 141–164. · Zbl 0846.65022
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.