Complexity of computing topological degree of Lipschitz functions in n dimensions
From authors' summary: We find lower and upper bounds on the complexity, comp, of computing the topological degree of functions defined on the n- dimensional unit cube \(C^ n\), \(f: C^ n\to R^ n\), \(n\geq 2\), which satisfy a Lipschitz condition with constant K and whose infinity norm at each point on the boundary of \(C^ n\) is at least d, \(d>0\), and such that K/8d\(\geq 1\). A lower bound, \(comp_{low}\simeq 2n(K/8d)^{n- 1}(c+n)\) is obtained for comp, assuming that each function evaluation costs c and elementary arithmetic operations and comparisons cost unity. We prove that the topological degree can be computed using \(([K/2d+1]+1)^ n-([K/2d+1]-1)^ n\) function evaluations. It can be done by an algorithm due to Kearfott.
- An Optimal Complexity Algorithm for Computing the Topological Degree in Two Dimensions
- Computing the topological degree with noisy information
- Computing topological degree using noisy information
- Effective topological degree computation based on interval arithmetic
- Zur numerischen Bestimmung des Abbildungsgrades im \(R^ n\). II
- A simplification of Stenger's topological degree formula
- An algorithm for numerical calculation of topological degree
- An efficient degree-computation method for a generalized method of bisection
- Bisection is optimal
- Complexity of computing topological degree of Lipschitz functions in n dimensions
- Computing the topological degree of a mapping in \(R^n\)
- scientific article; zbMATH DE number 3688714 (Why is no real title available?)
- scientific article; zbMATH DE number 3438078 (Why is no real title available?)
- scientific article; zbMATH DE number 3381785 (Why is no real title available?)
- On the construction of sufficient refinements for computation of topological degree
- Perspectives on information-based complexity
- Optimal solution of nonlinear equations
- Randomization for continuous problems
- Computing the topological degree with noisy information
- ``Curse of dimensionality for complexity of approximation for classes of functions satisfying Lipschitz condition
- Quasi-decidability of a fragment of the first-order theory of real numbers
- COMPUTING TWO LINCHPINS OF TOPOLOGICAL DEGREE BY A NOVEL DIFFERENTIAL EVOLUTION ALGORITHM
- An Optimal Complexity Algorithm for Computing the Topological Degree in Two Dimensions
- Effective topological degree computation based on interval arithmetic
- Complexity of computing topological degree of Lipschitz functions in n dimensions
- On the complexity of isolating real roots and computing with certainty the topological degree
- Computing topological degree using noisy information
- Existence and computation of short-run equilibria in economic geography
This page was built for publication: Complexity of computing topological degree of Lipschitz functions in n dimensions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q578854)
