Effective Topological Degree Computation Based on Interval Arithmetic

0431141 - ÚI 2015 RIV US eng J - Journal Article
Franek, Peter - Ratschan, Stefan
Effective Topological Degree Computation Based on Interval Arithmetic.
Mathematics of Computation. Roč. 84, č. 293 (2015), s. 1265-1290. ISSN 0025-5718. E-ISSN 1088-6842
R&D Projects: GA ČR GCP202/12/J060
Institutional support: RVO:67985807
Keywords : computational topology * interval computation
Subject RIV: BA - General Mathematics
Impact factor: 1.464, year: 2015
http://www.ams.org/journals/mcom/0000-000-00/S0025-5718-2014-02877-9/

We describe a new algorithm for calculating the topological degree deg (f, B, 0) where B \subseteq Rn is a product of closed real intervals and f : B \to Rn 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 also present computational experiments based on an implementation of the algorithm. Also, 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.
Permanent Link: http://hdl.handle.net/11104/0235754