Complexity of Bezout's Theorem VI: Geodesics in the Condition (Number) Metric

2007/02/12 by Michael Shub, Shub, Michael
Computer Science · Engineering · #65H10 #65H20 #Advanced Numerical Analysis Techniques #Computational Geometry and Mesh Generation #FOS: Mathematics #Numerical Analysis (math.NA) #Polynomial and algebraic computation

paper · pdf · doi:10.48550/arxiv.math/0702344

openalex publication_date 2007/02/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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.

Related

• Geodesic complexity of a cube
• The geodesic complexity of n-dimensional Klein bottles
• Geodesic complexity for non-geodesic spaces
• Shortest k-Geodesics on Hyperbolic Surfaces
• Efficient geodesics and an effective algorithm for distance in the complex of curves