zbMATH — the first resource for mathematics

Topology for computing. (English) Zbl 1065.68001
Cambridge Monographs on Applied and Computational Mathematics 16. Cambridge: Cambridge University Press (ISBN 0-521-83666-2/hbk). xiii, 243 p. (2005).
A number of current problems in computation require that one be able to get the topology right. Thus in showing a geometric figure it is important to display it (and indeed model it) with the correct number of holes. Likewise in structural biology it can be important to compute linking numbers of molecular structures, thus models of the molecule should be accurate enough to yield the correct value. Algebraic topology provides a natural framework for problems of this kind. However if one is interested in computing actual numbers for such things the normal methods of algebraic topology do not provide computationally effective algorithms. The aim of this book is threefold. Firstly to introduce the basic concepts of topology, specifically homology and Morse-Smale decomposition of manifolds. Secondly to show computationally effective means for calculating certain topological invariants. Lastly to give examples with timings and statistics to justify the claim that the methods are effective.
In part one of the book the review of homology and Morse-Smale theory covers the basic ideas. For homology the exposition concentrates on the case of coefficients in a field, although the more general case is covered. For Morse-Smale theory the concentration is on surfaces, in this case because the algorithms presented do not easily generalize to higher dimensions. A central notion of computation of topological invariants is persistence. To describe the idea suppose that one has a filtration on a complex then a cycle may appear at one level and (perhaps) disappear at a subsequent one. Cycles that survive for many levels of the filtration are persistent. From the point of view of computing homology it would be nice if one could find a filtration in which the only persistent cycles were the ones that live for ever. Persistence thus forms the basis for the algorithms described in the book. In part two the algorithms for computing homology are defined. Algorithms for reordering a filtration so that the computation becomes faster, essentially by identifying the simplexes that introduce each cycle and also those that eliminate them, are described. Part two also describes how one can construct a Morse-Smale decomposition of a surface starting from a triangulation of the surface. In the last part the author presents some comments on the implementation of the algorithms. The experiments show that performance is in practice much better than worst-case analysis would suggest.

68-02 Research exposition (monographs, survey articles) pertaining to computer science
55-04 Software, source code, etc. for problems pertaining to algebraic topology
57-04 Software, source code, etc. for problems pertaining to manifolds and cell complexes
68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
68U10 Computing methodologies for image processing
Full Text: DOI