Effective Topological Degree Computation Based on Interval Arithmetic

0431141 - ÚI 2015 RIV US eng J - Článek v odborném periodiku
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
Grant CEP: GA ČR GCP202/12/J060
Institucionální podpora: RVO:67985807
Klíčová slova: computational topology * interval computation
Kód oboru RIV: BA - Obecná matematika
Impakt faktor: 1.464, rok: 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.
Trvalý link: http://hdl.handle.net/11104/0235754