×

Coreduction homology algorithm for regular CW-complexes. (English) Zbl 1229.55001

Let \(S\) denote the cells of a CW-complex with incidence map \(\kappa\), so that the boundary operator is \(\partial s=\sum_{t\in S}\kappa(s,t)t\). A pair of cells \((a,b)\) is said to be a reduction pair if \(\kappa(b,a)\neq 0\) and either \(a\) is the only cell in the boundary of \(b\), or \(b\) is the only cell whose boundary contains \(a\). The set \(S\setminus\{a,b\}\) is called a reduction of \(S\), and although it is not necessarily a CW-complex, it does form a chain complex with incidence map induced by \(\kappa\). In fact, the homologies of \(S\) and its reduction are isomorphic. Since the computation of the homology of \(S\) using the standard Smith normal form algorithm has time complexity that is polynomial in the number of cells, finding a sequence of reductions of \(S\) may reduce the computational time simply by reducing the number of cells.
The authors of the article show that a finite regular CW-complex embedded in the plane can be reduced in linear time to a disjoint collection of 1-cells, the number of which gives the first Betti number. In particular, one does not need to know the specific values of the incidence map: knowledge of the facets of each cell suffice. In general however, one needs to compute the incidence map, which for a regular complex takes on the values \(0,\pm 1\). The authors provide a general algorithm for determining the incidence map for a regular finite CW-complex, as well as an explicit formula for the incidence map in the special case of a rectangular CW-complex – where each cell is given in terms of a product of intervals. The article concludes with a section that summarizes the results of numerical experiments using their methods.
Readers of the article are assumed to be familiar with elementary topology and homology. A knowledge of CW-complexes is useful.

MSC:

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)

Software:

CAPD; Homology
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Adler, R.J., Taylor, J.E.: Random Fields and Geometry. Springer, New York (2007) · Zbl 1149.60003
[2] Blömker, D., Maier-Paape, S., Wanner, T.: Phase separation in stochastic Cahn-Hilliard models. In: Miranville, A. (ed.) Mathematical Methods and Models in Phase Transitions, pp. 1–41. Nova Science, New York (2005)
[3] Bredon, G.E.: Topology and Geometry. Graduate Texts in Mathematics, vol. 139. Springer, New York (1997) · Zbl 0934.55001
[4] Day, S., Kalies, W.D., Mischaikow, K., Wanner, T.: Probabilistic and numerical validation of homology computations for nodal domains. Electron. Res. Announc. Am. Math. Soc. 13, 60–73 (2007) · Zbl 1141.60025 · doi:10.1090/S1079-6762-07-00175-8
[5] Day, S., Kalies, W.D., Wanner, T.: Verified homology computations for nodal domains. SIAM J. Multiscale Model. Simul. 7(4), 1695–1726 (2009) · Zbl 1201.60034 · doi:10.1137/080735722
[6] Delfinado, C.J.A., Edelsbrunner, H.: An incremental algorithm for Betti numbers of simplicial complexes. In: SCG ’93: Proceedings of the Ninth Annual Symposium on Computational Geometry, pp. 232–239. ACM, New York (1993)
[7] Dumas, J.-G., Heckenbach, F., Saunders, D., Welker, V.: Computing simplicial homology based on efficient Smith normal form algorithms. In: Algebra, Geometry, and Software Systems, pp. 177–206. Springer, Berlin (2003) · Zbl 1026.55010
[8] Edelsbrunner, H., Letscher, D., Zomorodian, A.: Topological persistence and simplification. Discrete Comput. Geom. 28(4), 511–533 (2002) · Zbl 1011.68152 · doi:10.1007/s00454-002-2885-2
[9] Friedman, J.: Computing Betti numbers via combinatorial Laplacians. Algorithmica 21(4), 331–346 (1998) · Zbl 0911.57021 · doi:10.1007/PL00009218
[10] Gameiro, M., Mischaikow, K., Wanner, T.: Evolution of pattern complexity in the Cahn-Hilliard theory of phase separation. Acta Mater. 53(3), 693–704 (2005) · doi:10.1016/j.actamat.2004.10.022
[11] Juda, M., Mrozek, M.: \(\mathbb{Z}\)2-homology of weak 2-pseudomanifolds may be computed in O(n {\(\alpha\)}(n)) time. Preprint, Jagiellonian University, Computer Science Department (2010). Available online at http://www.ii.uj.edu.pl/\(\sim\)mrozek/papers/homology-of-2-manifolds-15.pdf · Zbl 1276.55003
[12] Kaczynski, T., Mischaikow, K., Mrozek, M.: Computing homology. Homology Homotopy Appl. 5(2), 233–256 (2003) · Zbl 1028.55001
[13] Kaczynski, T., Mischaikow, K., Mrozek, M.: Computational Homology. Applied Mathematical Sciences, vol. 157. Springer, New York (2004) · Zbl 1039.55001
[14] Kaczynski, T., Mrozek, M., Ślusarek, M.: Homology computation by reduction of chain complexes. Comput. Math. Appl. 35(4), 59–70 (1998) · Zbl 0904.55004 · doi:10.1016/S0898-1221(97)00289-7
[15] Massey, W.S.: A Basic Course in Algebraic Topology. Graduate Texts in Mathematics, vol. 127. Springer, New York (1991) · Zbl 0725.55001
[16] Mischaikow, K., Wanner, T.: Probabilistic validation of homology computations for nodal domains. Ann. Appl. Probab. 17(3), 980–1018 (2007) · Zbl 1131.60047 · doi:10.1214/105051607000000050
[17] Mischaikow, K., Wanner, T.: Topology-guided sampling of nonhomogeneous random processes. Ann. Appl. Probab. 20(3), 1068–1097 (2010) · Zbl 1213.60072 · doi:10.1214/09-AAP652
[18] Mrozek, M.: Cech type approach to computing homology of maps. Discrete Comput. Geom. 44(3), 546–576 (2010) · Zbl 1219.55004 · doi:10.1007/s00454-010-9255-2
[19] Mrozek, M., Batko, B.: Coreduction homology algorithm. Discrete Comput. Geom. 41(1), 96–118 (2009) · Zbl 1163.68041 · doi:10.1007/s00454-008-9073-y
[20] Mrozek, M., Pilarczyk, P., \.Zelazna, N.: Homology algorithm based on acyclic subspace. Comput. Math. Appl. 55(11), 2395–2412 (2008) · Zbl 1142.15300 · doi:10.1016/j.camwa.2007.08.044
[21] Mrozek, M., Wanner, T.: Coreduction homology algorithm for inclusions and persistent homology. Comput. Math. Appl. (in press) · Zbl 1207.57001
[22] Munkres, J.R.: Elements of Algebraic Topology. Addison-Wesley, Menlo Park (1984) · Zbl 0673.55001
[23] Peltier, S., Ion, A., Kropatsch, W., Damiand, G., Haxhimusa, Y.: Directly computing the generators of image homology using graph pyramids. Image Vis. Comput. 27(7), 846–853 (2009) · Zbl 05842136 · doi:10.1016/j.imavis.2008.06.009
[24] Storjohann, A.: Near optimal algorithms for computing smith normal forms of integer matrices. In: Proceedings of the 1996 International Symposium on Symbolic and Algebraic Computation, ISSAC ’96, pp. 267–274. ACM, New York (1996) · Zbl 0914.65043
[25] Wanner, T., Fuller Jr., E.R., Saylor, D.M.: Homological characterization of microstructure response fields in polycrystals. Acta Mater. 58(1), 102–110 (2010) · doi:10.1016/j.actamat.2009.08.061
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.