Verified homology computations for nodal domains

44. Sarah Day, William D. Kalies, Thomas Wanner:
    Verified homology computations for nodal domains
    SIAM Journal on Multiscale Modeling & Simulation 7(4), pp. 1695-1726, 2009.

Abstract

Homology has long been accepted as an important computational tool for quantifying complex structures. In many applications these structures arise as nodal domains of real-valued functions and are therefore amenable only to a numerical study based on suitable discretizations. Such an approach immediately raises the question of how accurately the resulting homology can be computed. In this paper we present an algorithm for correctly computing the homology of one- and two-dimensional nodal domains. The approach relies on constructing an appropriate cubical approximation for the nodal domain based on the behavior of the defining function at the vertices of a fixed grid. Betti numbers for these cubical sets are readily computable. Here, we present a technique to verify that the cubical representation is homeomorphic to the nodal domain, and therefore preserves homology. To illustrate this approach we consider examples from three classes of nodal domains, including the time-dependent patterns generated by the Cahn-Hilliard model for spinodal decomposition. We use these results to examine the probability of correct homology computations given specific grid sizes as related to the analytic estimates presented in earlier work.

Links

The published version of the paper can be found at https://doi.org/10.1137/080735722.

Bibtex

@article{day:etal:09a,
   author = {Sarah Day and William D. Kalies and Thomas Wanner},
   title = {Verified homology computations for nodal domains},
   journal = {SIAM Journal on Multiscale Modeling \& Simulation},
   year = 2009,
   volume = 7,
   number = 4,
   pages = {1695--1726},
   doi = {10.1137/080735722}
   }