Complexity of Bezout’s Theorem VI: Geodesics in the Condition (Number) Metric
Tóm tắt
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.
Tài liệu tham khảo
C. Beltran and L. M. Pardo, Smale’s 17th problem: A probabilistic positive solution, Found. Comput. Math. 7 (2007), 87–134.
C. Beltran and L. M. Pardo, Smale’s 17th problem: Average polynomial time to compute affine and projective solutions. Preprint.
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.
M. Gromov, Metric Structures for Riemannian and Non-Riemannian Spaces, Birkhäuser, Basel, 1998.
L. Blum, F. Cucker, M. Shub, and S. Smale, Complexity and Real Computation, Springer, Berlin, 1998.
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.
M. Shub and S. Smale, Complexity of Bezout’s theorem I: Geometrical aspects, J. Am. Math. Soc. 6 (1993), 459–501.
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.
M. Shub and S. Smale, Complexity of Bezout’s theorem III: Condition number and packing, J. Complex. 9 (1993), 4–14.
M. Shub and S. Smale, Complexity of Bezout’s theorem IV: Probability of success; extensions, SINUM 33 (1996), 128–148.
M. Shub and S. Smale, Complexity of Bezout’s theorem V: Polynomial time, Theor. Comput. Sci. 133 (1994), 141–164.