A randomized subdivision algorithm for determining the topology of nodal sets

52. Gregory S. Cochran, Thomas Wanner, Pawel Dlotko:
    A randomized subdivision algorithm for determining the topology of nodal sets
    SIAM Journal on Scientific Computing 35(5), pp. B1034-B1054, 2013.

Abstract

Topology is a natural mathematical tool for quantifying complex structures. In many applications, such as for example in the context of phase-field models in materials science, the structures of interest arise as sub- or superlevel sets of continuous functions, i.e., as nodal domains. From a computational point of view, any attempt at constructing a truthful representation of the topology of nodal domains has to involve a discretization step, and it is natural to wonder whether this step introduces topological artifacts. In this paper, we present a randomized subdivision algorithm which, given a smooth function, constructs an adaptive rectangular grid containing the essential information necessary for approximating nodal domains. Furthermore, under mild regularity assumptions the algorithm will also provide a computer-assisted proof for the correctness of the approximation by showing that the rectangular grid can be used to construct rectangular complexes which are homotopy equivalent to the nodal domains of the function. Our method extends the results of Day, Kalies, Wanner (2009), by employing a more accurate and efficient interval arithmetic range enclosure algorithm, as well as developing a randomized subdivision technique to virtually eliminate grid alignment effects.

Links

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

Bibtex

@article{cochran:etal:13a,
   author = {Gregory S. Cochran and Thomas Wanner and Pawe{\l} D{\l}otko},
   title = {A randomized subdivision algorithm for determining the
              topology of nodal sets},
   journal = {SIAM Journal on Scientific Computing},
   volume = {35},
   year = {2013},
   number = {5},
   pages = {B1034--B1054},
   doi = {10.1137/120903154}
   }