Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Effective topological degree computation based on interval arithmetic

Authors: Peter Franek and Stefan Ratschan
Journal: Math. Comp. 84 (2015), 1265-1290
MSC (2010): Primary 55-04, 68-04; Secondary 55P15
Published electronically: September 17, 2014
MathSciNet review: 3315508
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We describe a new algorithm for calculating the topological degree $ \mathrm {deg\,}(f,B,0)$ where $ B\subseteq \mathbb{R}^n$ is a product of closed real intervals and $ f:B\to \mathbb{R}^n$ is a real-valued continuous function given in the form of arithmetical expressions. The algorithm cleanly separates numerical from combinatorial computation. Based on this, the numerical part provably computes only the information that is strictly necessary for the following combinatorial part, and the combinatorial part may optimize its computation based on the numerical information computed before. We present computational experiments based on an implementation of the algorithm. In contrast to previous work, the algorithm does not assume knowledge of a Lipschitz constant of the function $ f$, and works for arbitrary continuous functions for which some notion of interval arithmetic can be defined.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 55-04, 68-04, 55P15

Retrieve articles in all journals with MSC (2010): 55-04, 68-04, 55P15

Additional Information

Peter Franek
Affiliation: Institute of Computer Science, Academy of Sciences of the Czech Republic — and — Faculty of Information Technology, Czech Technical University

Stefan Ratschan
Affiliation: Institute of Computer Science, Academy of Sciences of the Czech Republic

Received by editor(s): July 26, 2012
Received by editor(s) in revised form: May 18, 2013, and September 3, 2013
Published electronically: September 17, 2014
Additional Notes: This work was supported by the Czech Science Foundation (GAČR) grant number P202/12/J060 with institutional support RVO:67985807
Article copyright: © Copyright 2014 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society