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
DOI: https://doi.org/10.1090/S0025-5718-2014-02877-9
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?)

  • [1] Oliver Aberth, Computation of topological degree using interval arithmetic, and applications, Math. Comp. 62 (1994), no. 205, 171-178. MR 1203731 (94d:65031), https://doi.org/10.2307/2153402
  • [2] G. E. Alefeld, F. A. Potra, and Z. Shen, On the existence theorems of Kantorovich, Moore and Miranda, Topics in numerical analysis, Comput. Suppl., vol. 15, Springer, Vienna, 2001, pp. 21-28. MR 1874501, https://doi.org/10.1007/978-3-7091-6217-0_3
  • [3] Thomas Beelitz, Andreas Frommer, Bruno Lang, and Paul Willems, A framework for existence tests based on the topological degree and homotopy, Numer. Math. 111 (2009), no. 4, 493-507. MR 2471608 (2010f:65107), https://doi.org/10.1007/s00211-008-0193-3
  • [4] T. Boult and K. Sikorski, Complexity of computing topological degree of Lipschitz functions in $ n$ dimensions, J. Complexity 2 (1986), no. 1, 44-59. MR 925343 (89i:65051), https://doi.org/10.1016/0885-064X(86)90022-1
  • [5] L. E. J. Brouwer, Über Abbildung von Mannigfaltigkeiten, Math. Ann. 71 (1911), no. 1, 97-115 (German). MR 1511644, https://doi.org/10.1007/BF01456931
  • [6] Robert F. Brown, A Topological Introduction to Nonlinear Analysis, 2nd ed., Birkhäuser Boston Inc., Boston, MA, 2004. MR 2020421 (2004i:47125)
  • [7] A. Bruckner, J. Bruckner, and B. Thomson,
    Real Analysis.
    Prentice Hall PTR, 1997.
  • [8] Pieter Collins, Computability and representations of the zero set, Proceedings of the Fifth International Conference on Computability and Complexity in Analysis (CCA 2008), Electron. Notes Theor. Comput. Sci., vol. 221, Elsevier Sci. B. V., Amsterdam, 2008, pp. 37-43. MR 2873345 (2012m:03155), https://doi.org/10.1016/j.entcs.2008.12.005
  • [9] Jane Cronin, Fixed Points and Topological Degree in Nonlinear Analysis, Mathematical Surveys, No. 11, American Mathematical Society, Providence, R.I., 1964. MR 0164101 (29 #1400)
  • [10] Jianwei Dian and R. Baker Kearfott, Existence verification for singular and nonsmooth zeros of real nonlinear systems, Math. Comp. 72 (2003), no. 242, 757-766. MR 1954966 (2004a:65056), https://doi.org/10.1090/S0025-5718-02-01427-8
  • [11] Pavel Drábek and Jaroslav Milota, Methods of Nonlinear Analysis, Birkhäuser Advanced Texts: Basler Lehrbücher. [Birkhäuser Advanced Texts: Basel Textbooks], Birkhäuser Verlag, Basel, 2007. Applications to differential equations. MR 2323436 (2008i:47134)
  • [12] P. J. Erdelsky, Computing the Brouwer degree in $ R^{2}$, Math. Comp. 27 (1973), 133-137. MR 0326990 (48 #5332)
  • [13] Irene Fonseca and Wilfrid Gangbo, Degree Theory in Analysis and Applications, Oxford Lecture Series in Mathematics and its Applications, vol. 2, The Clarendon Press Oxford University Press, New York, 1995. Oxford Science Publications. MR 1373430 (96k:47100)
  • [14] P. Franek, S. Ratschan, and P. Zgliczynski,
    Quasi-decidability of a fragment of the first-order theory of real numbers,
    http://www2.cs.cas.cz/~ratschan/papers/quasidec_constr.pdf, 2012
    (preprint).
  • [15] Andreas Frommer and Bruno Lang, Existence tests for solutions of nonlinear equations using Borsuk's theorem, SIAM J. Numer. Anal. 43 (2005), no. 3, 1348-1361 (electronic). MR 2177808 (2006g:65081), https://doi.org/10.1137/S0036142903438148
  • [16] A. Frommer, B. Lang, and M. Schnurr, A comparison of the Moore and Miranda existence tests, Computing 72 (2004), no. 3-4, 349-354. MR 2081828 (2005i:65079), https://doi.org/10.1007/s00607-004-0064-4
  • [17] Massimo Furi, Maria Patrizia Pera, and Marco Spadini, A set of axioms for the degree of a tangent vector field on differentiable manifolds, Fixed Point Theory Appl. (2010), Art. ID 845631, 11. MR 2645107 (2011d:55003)
  • [18] T. J. Hickey.
    smathlib.
    http://interval.sourceforge.net/interval/prolog/clip/clip/smath/README.html.
  • [19] Morris W. Hirsch, Differential Topology, Springer-Verlag, New York, 1976, Graduate Texts in Mathematics, No. 33. MR 0448362 (56 #6669)
  • [20] Anatole Katok and Boris Hasselblatt, Introduction to the Modern Theory of Dynamical Systems, Encyclopedia of Mathematics and its Applications, vol. 54, Cambridge University Press, Cambridge, 1995. With a supplementary chapter by Katok and Leonardo Mendoza. MR 1326374 (96c:58055)
  • [21] Baker Kearfott, An efficient degree-computation method for a generalized method of bisection, Numer. Math. 32 (1979), no. 2, 109-127. MR 529902 (80g:65062), https://doi.org/10.1007/BF01404868
  • [22] R. Baker Kearfott, Jianwei Dian, and A. Neumaier, Existence verification for singular zeros of complex nonlinear systems, SIAM J. Numer. Anal. 38 (2000), no. 2, 360-379. MR 1770053 (2001e:65078), https://doi.org/10.1137/S0036142999361074
  • [23] R. Baker Kearfott and Jianwei Dian, Existence verification for higher degree singular zeros of nonlinear systems, SIAM J. Numer. Anal. 41 (2003), no. 6, 2350-2373. MR 2034619 (2004i:65045), https://doi.org/10.1137/S0036142901386057
  • [24] Wieslaw Krawcewicz and Jianhong Wu, Theory of Degrees with Applications to Bifurcations and Differential Equations, Canadian Mathematical Society Series of Monographs and Advanced Texts, John Wiley & Sons Inc., New York, 1997. A Wiley-Interscience Publication. MR 1426128 (97j:47083)
  • [25] J. Mawhin, Topological Degree Methods in Nonlinear Boundary Value Problems, CBMS Regional Conference Series in Mathematics, vol. 40, American Mathematical Society, Providence, R.I., 1979. Expository lectures from the CBMS Regional Conference held at Harvey Mudd College, Claremont, Calif., June 9-15, 1977. MR 525202 (80c:47055)
  • [26] John W. Milnor, Topology from the Differentiable Viewpoint, Princeton Landmarks in Mathematics, Princeton University Press, Princeton, NJ, 1997. Based on notes by David W. Weaver; Revised reprint of the 1965 original. MR 1487640 (98h:57051)
  • [27] Carlo Miranda, Un'osservazione su un teorema di Brouwer, Boll. Un. Mat. Ital. (2) 3 (1940), 5-7 (French). MR 0004775 (3,60b)
  • [28] Ramon E. Moore, R. Baker Kearfott, and Michael J. Cloud, Introduction to Interval Analysis, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2009. MR 2482682 (2010d:65106)
  • [29] K. Nakakura and S. Murashige,
    Numerical Computation of the Mapping Degree Using Computational Homology.
    In Proceedings of the 12th GAMM - IMACS International Symposium on Scientific Computing, Computer Arithmetic and Validated Numerics, SCAN '06, page 34, Washington, DC, USA, 2006. IEEE Computer Society.
  • [30] Arnold Neumaier, Interval Methods for Systems of Equations, Encyclopedia of Mathematics and its Applications, vol. 37, Cambridge University Press, Cambridge, 1990. MR 1100928 (92b:65004)
  • [31] T. O'Neil and J. W. Thomas, The calculation of the topological degree by quadrature, SIAM J. Numer. Anal. 12 (1975), no. 5, 673-680. MR 0411134 (53 #14873)
  • [32] Donal O'Regan, Yeol Je Cho, and Yu-Qing Chen, Topological Degree Theory and Applications, Series in Mathematical Analysis and Applications, vol. 10, Chapman & Hall/CRC, Boca Raton, FL, 2006. MR 2223854 (2007b:47168)
  • [33] L. B. Rall, A comparison of the existence theorems of Kantorovich and Moore, SIAM J. Numer. Anal. 17 (1980), no. 1, 148-161. MR 559469 (81k:65052), https://doi.org/10.1137/0717015
  • [34] Siegfried M. Rump, Verification methods: rigorous results using floating-point arithmetic, Acta Numer. 19 (2010), 287-449. MR 2652784 (2011j:65093), https://doi.org/10.1017/S096249291000005X
  • [35] F. Sauvigny,
    Brouwer's degree of mapping with geometric applications.
    In Partial Differential Equations 1, Universitext, pages 175-214. Springer Berlin Heidelberg, 2006.
  • [36] Frank Stenger, Computing the topological degree of a mapping in $ {\bf R}^{n}$, Numer. Math. 25 (1975/76), no. 1, 23-38. MR 0394639 (52 #15440)
  • [37] Martin Stynes, A simplification of Stenger's topological degree formula, Numer. Math. 33 (1979), no. 2, 147-155. MR 549445 (80m:55002), https://doi.org/10.1007/BF01399550
  • [38] H. Tietze,
    Über Funktionen, die auf einer abgeschlossenen Menge stetig sind,
    Journal für Die Reine und Angewandte Mathematik, 145:9-14, 1915.

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
Email: franek@cs.cas.cz, peter.franek@fit.cvut.cz

Stefan Ratschan
Affiliation: Institute of Computer Science, Academy of Sciences of the Czech Republic
Email: stefan.ratschan@cs.cas.cz

DOI: https://doi.org/10.1090/S0025-5718-2014-02877-9
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