next up previous contents
Next: 1.5 Fiber Bundles Up: 1. Mathematical Concepts Previous: 1.3 Topological Toolkit


1.4 Computational Topology

The previous sections introduced combinatorial concepts for CW-complex representations and abstract classification mechanisms to manage scientific data. Compared to the theory of CW-complexes, this section focuses more on the details of algebraic properties of linear mappings by a procedure to associate a sequence of Abelian groups or modules with, e.g., a topological space. Only a few concepts are introduced in this section [55,22], because of the fact that computational topology [56,19] is a complex and emerging part of scientific computing in its own right.

The motivation for this section is to retain the structure of geometrical objects and even physical field approximations for computational mechanisms, because the recovery of lost structural information of objects has proven to be a very complex and difficult tasks.

1.4.1 Chains

To use the elements of a dimension of a cell complex, e.g., all edges, in a computational manner, a mapping of the $ p$ -cells onto an algebraic structure is needed. An algebraic representation of the assembly of cells with a given orientation is thereby made available. Whereas the cell topology is concerned about the internal structure of a given cell, the chain concept acts on certain $ p$ -cells. A formal definition for a $ p$ -chain ($ p^{th}$ chain group) is given by:

Definition 20 (P-Chain)   A $ p$ -chain $ c_p$ defined over a cell complex $ {\ensuremath{\mathfrak{K}}}$ and a vector space $ {\ensuremath{\mathcal{V}}}$ is a formal sum

$\displaystyle c_p = \sum_{i=1}^{n_p}w_i \ensuremath{\tau_{p}^{i}} \quad \quad \...
...au_{p}^{i}} \in {\ensuremath{\mathfrak{K}}}, w_i \in {\ensuremath{\mathcal{V}}}$ (1.24)

respecting that the operation is closed under orientation reversal:

$\displaystyle \forall \ensuremath{\tau_{p}^{i}} \in c_p \;\; \textnormal{there is} \; -\ensuremath{\tau_{p}^{i}} \in c_p$ (1.25)

All different topological parts are called cells, and the dimensionality is expressed by adding the dimension such as a 3-cell for a volume, a 2-cell for surface elements, a 1-cell for lines, and a 0-cell for vertices.

Thus, two $ p$ -chains can be added, or a $ p$ -chain can be multiplied by a scalar. In addition, $ p$ -chains support algebraic-topological operations, including the boundary and coboundary operations. Based on these concepts, a cell complex can be seen as a formal structure where cells can be added, subtracted, and multiplied. The cell complexes used in this work have a chain group in every dimension. Homological concepts are applied here for the first time, due to the fact that homology examines the connectivity between two immediate dimensions. A structure-relating map between sets of chains $ C_p$ is therefore introduced1.2.

Definition 21 (Boundary Homomorphism)   Let $ {\ensuremath{\mathfrak{K}}}$ be a cell complex and $ \tau_{p}^{i} \in
{\ensuremath{\mathfrak{K}}}, \tau_{p}^{i} =\{k_0, k_1, ..,k_p\}$ . The boundary homomorphism $ \partial_p: C_p({\ensuremath{\mathfrak{K}}}) \rightarrow
C_{p-1}({\ensuremath{\mathfrak{K}}})$ is:

$\displaystyle \partial_p \tau_{p}^{i} = \sum_i (-1)^i [k_0, k_1, .., \tilde k_i, ...k_n]$ (1.26)

where $ \tilde k_i$ indicates that $ k_i$ is deleted from the sequence.

This can be seen as a boundary operator, that maps $ p$ -chains onto the $ p-1$ -chains in their boundary. It should not be confused with the geometric boundary of a point set. This algebraic-topological operation defines a $ (p-1)$ -chain in terms of a $ p$ -chain. It is compatible with the additive and the external multiplicative structure of chains and builds a linear transformation:

$\displaystyle C_{p} \xrightarrow{\partial_p} C_{p-1}$ (1.27)

Therefore, the boundary operator can be used linearly

$\displaystyle \partial \left ( \sum_i w_i \tau^i_{p} \right ) = \sum_i w_i (\partial \tau^i_{p})$ (1.28)

which means that the boundary operator can be used separately for each cell. The cell complex properties can be easily calculated by means of chains. 3-cells intersect on 2-cells or have an empty intersection. This operation can be described by the boundary operator $ \partial c_{p}$ of the cell complex and the corresponding orientation induced on them:

Definition 22 (Cell complex)   A cell complex $ {\ensuremath{\mathfrak{K}}}$ is a set of cells that satisfy the following properties:

\small\psfrag{a} [c]{$\tau_{1}^1$}\psfrag{b} [c...
...e=figures/pchain_boundary_01.eps, width=0.5\textwidth}\end{center}\end{figure}
Figure 1.8: Representation of a 1-chain with boundary (left) and a 2-chain with boundary (right).

Figure 1.8 depicts two examples of 1-chains, 2-chains, and an example of the boundary operator. Applying the appropriate boundary operator to the 2-chain example read:

$\displaystyle \partial_2 \tau_{2} = \tau_{1}^1 + \tau_{1}^2 + \tau_{1}^3 + \tau_{1}^4$ (1.29)
$\displaystyle \partial_1 \left ( \tau_{1}^1 + \tau_{1}^2 + \tau_{1}^3 + \tau_{1...
...\tau_{0}^2 + \tau_{0}^3 - \tau_{0}^3 + \tau_{1}^4 - \tau_{1}^4 - \tau_{0}^1 = 0$ (1.30)

Using the boundary operator on a sequence of chains of different dimensions, a chain complex is obtained:

Definition 23 (Chain Complex)   A chain complex $ C_{*} = \{C_p, \partial_p\}$ is a sequence of modules $ C_p$ over a ring $ R$ and a sequence of homomorphisms

$\displaystyle \partial_p : C_p \rightarrow C_{p-1}$ (1.31)

such that

$\displaystyle \partial_{p-1} \partial_{p} = 0$ (1.32)

1.4.2 Cochains

Before the introduction of the concept of chains only the simple structure of a cell complex was available. The cell complex only contains the set of cells and their connectivity. The introduction of the chain concept provides the concept of an assembly of cells and the corresponding algebraic structure. Chains can be seen as mappings from oriented cells as part of a cell complex to another space. This definition establishes the algebraic access of computational methods to handle the concept of a cell complex.

In addition to cell complexes, scientific computing requires the notation and access mechanisms to global quantities related to macroscopic $ p$ -dimensional space-time domains, introduced in Section 1.2. This collection of possible quantities, which can be measured, can then be called a field, which permits the modeling of these measurements as a field function that can be integrated on arbitrary $ p$ -dimensional (sub)domains. An important fact which has to be stated here is that all quantities which can be measured are always attached to a finite region of space. A field function can then be seen as the abstracted process of measurement of this quantity [31,35]. The concept of cochains allows the association of numbers not only to single cells, as chains do, but also to assemblies of cells. Briefly, the necessary requirements are that this mapping is not only orientation-dependent, but also linear with respect to the assembly of cells, modeled by chains. A cochain representation is now the global quantity association with subdomains of a cell complex, which can be arbitrarily built to discretize a domain. Physical fields therefore manifest on a linear assembly of cells. Based on cochains, topological laws can be given a discrete representation.

Definition 24 (Cochains [25])   A linear transformation $ \sigma$ of the $ p$ -chains into the field $ \mathbb{R}$ of real numbers forms a vector space $ c_{p} \xrightarrow{\sigma} \mathbb{R}$ and is called a vector valued $ p$ -dimensional cochain or short $ p$ -cochain.

The space of all linear mappings on $ c_p$ is denoted by $ C^p$ , where the elements of $ C^p$ are called cochains. Cochains express a representation for fields over a discretized domain $ {\ensuremath{\mathfrak{K}}}$ . Addition and multiplication by a scalar are defined for the field functions and so for cochains. To extend the expression possibilities, coboundaries of cochains are introduced.

Definition 25 (Coboundary)   The coboundary $ \delta$ of a $ p$ -cochain is a $ (p+1)$ -cochain defined as:

$\displaystyle \delta c^p = \sum_i v_i \tau_i, \quad \textnormal{where} \quad v_i = \sum_{b \in  \textnormal{faces}(\tau_i)} \sigma(b,\tau_i) c_p(b)$ (1.33)

Thus, the coboundary operator assigns non-zero coefficients only to those $ (p+1)$ cells that have $ c_p$ as a face. As can be seen, $ \delta
c_p$ depends not only on $ c_p$ but on how $ c_p$ lies in the complex $ {\ensuremath{\mathfrak{K}}}$ . This is a fundamental difference between the two operators $ \partial$ and $ \delta$ . An example is given in Figure 1.9 where the coboundary operator is used on a 1-cell. The coboundary of a $ p$ -cochain is a $ p+1$ cochain which assigns to each $ (p+1)$ cell the sum of the values that the $ p$ -cochains assigns to the $ p$ -cells which form the boundary of the $ (p+1)$ cell. Each quantity appears in the sum multiplied by the corresponding incidence number. Cochain complexes [53,22] are defined similarly to chain complexes except that the arrows are reversed.

Definition 26 (Cochain Complex)   A cochain complex $ C^{*} = \{C^p, \delta^p\}$ is a sequence of modules $ C^p$ and homomorphisms:

$\displaystyle \delta^p : C^p \rightarrow C^{p+1}$ (1.34)

such that

$\displaystyle \delta^{p+1} \delta^{p} = 0$ (1.35)

Then, the following sequence with $ \delta \delta = 0$ is generated:

$\displaystyle 0 \xrightarrow{\delta} C^0 \xrightarrow{\delta} C^1 \xrightarrow{\delta} C^2 \xrightarrow{\delta} C^3 \xrightarrow{\delta} 0$ (1.36)

Figure: Cochain complex with the corresponding coboundary operator: $ {\ensuremath{\mathfrak{K}}}^1 \xrightarrow{\delta} \delta {\ensuremath{\mathfrak{K}}}^1 \xrightarrow{\delta} \delta \delta {\ensuremath{\mathfrak{K}}}^1 = 0$
\small\psfrag{T} [c]{{\ensuremath{\mathcal{T_P}}}...
...gure=figures/cochain_complex.eps, width=0.9\textwidth}\end{center}\end{figure}

1.4.3 Homology and Cohomology

The concepts of chains can also be used to characterize properties of spaces, the homology and cohomology where it is only necessary to use $ C_p({\ensuremath{\mathfrak{K}}}, \mathbb{Z})$ . The algebraic structure of chains is an important concept, e.g., to detect a $ p$ -dimensional hole that is not the boundary of a $ p+1$ -chain, which is called a $ p$ -cycle.

Definition 27 (Cycle)   The $ p^{th}$ cycle (group) is $ Z_p = {\ensuremath{\textnormal{ker} \; {\partial_p}}}$ . A chain which is an element of $ Z_p$ is a k-cycle.

In other words, a cycle is a chain whose boundary is $ \partial_p C_p =
0$ , a closed chain. The already introduced boundary concept can also be related to homological terms:

Definition 28 (Boundary)   The $ p^{th}$ boundary (group) is $ B_p = {\ensuremath{\textnormal{im} \; {\partial_{p+1}}}}$ . A chain which is an element of $ B_p$ is a p-boundary.

Or, a boundary is a chain $ D_p$ for which there is a chain $ C_p$ such that $ \partial_p C_p = D_p$ . As introduced, the set of all n-cycles $ Z_n$ and the set of all n-boundaries $ B_n$ are vector spaces over $ {\ensuremath{\mathbb{Z}}}_2$ . Since $ \partial^2 = 0$ , $ B_n \subset Z_n$ is obtained. The homology is then defined by $ H_n = Z_n /B_n$ . The homology of a space is a sequence of vector spaces. The topological classification of homology is introduced [19] by $ B_p = {\ensuremath{\textnormal{im} \; {\partial_{p+1}}}}$ and $ Z_p = {\ensuremath{\textnormal{ker} \; {\partial_p}}}$ so that $ B_p \subset Z_p$ and $ H_p =
Z_p / B_p$ where $ \beta_p = \textnormal{Rank} H_p$ . For cohomology $ B^p = {\ensuremath{\textnormal{im} \; {d^{p+1}}}}$ and $ Z^p = {\ensuremath{\textnormal{ker} \; {d^p}}}$ so that $ B^p
\subset Z^p$ and $ H^p = Z^p / B^p$ where $ \beta^p = \textnormal{Rank} H^p$ .

Figure 1.10 depicts the homology of the three-dimensional chain complex with the respective images and kernels, where the chain complex of $ {\ensuremath{\mathfrak{K}}}$ is defined by $ {\ensuremath{\textnormal{im} \; {\partial_{p+1}}}} \subseteq
{\ensuremath{\textnormal{ker} \; {\partial_p}}}$ . As can be seen, the boundary operator expression yields $ \partial_p \partial_{p+1} = 0$

\small\psfrag{C3} [c]{$C_3$}\psfrag{C2} [c]{$C_...
...igures/chaincomplex_homology.eps, width=0.6\textwidth}\end{center}\end{figure}
Figure 1.10: A graphical representation of (co)homology for a three-dimensional cell complex.

The first homology group [53] is the set of closed 1-chains (curves) in a space, modulo the closed 1-chains which are also boundaries. In the remainder of this work the ring $ R$ will be $ \mathbb{R}$ or $ \mathbb{Z}$ , in which case the modules $ C_p$ are vector spaces or Abelian groups, respectively, e.g., for $ \mathbb{R}$ the chain complex is given by $ C_{*}({\ensuremath{\mathfrak{K}}}; \mathbb{R} =
\{C_p({\ensuremath{\mathfrak{K}}};\mathbb{R}), \partial_p\}$ or for the coefficient group $ \mathbb{Z}$ the following cochain complex $ C_{*}({\ensuremath{\mathfrak{K}}}; \mathbb{Z} = \{C_p({\ensuremath{\mathfrak{K}}};\mathbb{Z}),
\partial_p\})$ .

\small\psfrag{phi} [c]{$\phi$}
\epsfig{figure=figures/homology_02.eps, width=0.22\textwidth}\end{center}\end{figure}
Figure 1.11: Illustration of cycles $ A,B,C$ and a boundary $ C$. $ A,B$ are not boundaries.

To give an example, the first homology group is the set of closed $ 1$ -chains (curves) modulo the closed $ 1$ -chains which are also boundaries. This group is denoted $ H_1 = Z_1/B_1$ , where $ Z$ are cycles or closed 1-chains and $ B$ are $ 1$ -boundaries. Another example is given in Figure 1.11.

1.4.4 Duality between Chains and Cochains

The concepts of chains and cochains coincide on finite complexes [55]. Geometrically, however, $ C_p$ and $ C^p$ are distinct [25] despite an isomorphism. An element of $ C_p$ is a formal sum of $ p$ -cells, where an element of $ C^p$ is a linear function that maps elements of $ C_p$ into a field. Chains are dimensionless multiplicities, whereas those associated with cochains are physical quantities [35]. The extension of cochains from single cell weights to quantities associated with assemblies of cells is not trivial and makes cochains very different from chains, even on finite cell complexes. Nevertheless, there is an important duality between $ p$ -chains and $ p$ -cochains.

For a chain $ c_p \in C_p({\ensuremath{\mathfrak{K}}},\mathbb{R})$ and a cochain $ c^p \in C^p({\ensuremath{\mathfrak{K}}},\mathbb{R})$ , the integral of $ c^p$ over $ c_p$ is denoted by $ \int_{c_p} c^p$ , and integration can be regarded as a mapping, where $ n$ represents the corresponding dimension:

$\displaystyle \int :C_p({\ensuremath{\mathfrak{K}}}) \times C^p({\ensuremath{\mathfrak{K}}}) \rightarrow \mathbb{R}, \qquad \textnormal{for} \; 0 \leq p \leq n$ (1.37)

Integration in the context of cochains is a linear operation: given $ a_1, a_2 \in \mathbb{R}, c^{p,1} c^{p,2} \in C^p({\ensuremath{\mathfrak{K}}})$ and $ c_p \in C_p({\ensuremath{\mathfrak{K}}})$ , reads

$\displaystyle \int_{c_p} a_1 c^{p,1} + a_2 c^{p,2} = a_1 \int_{c_p} c^{p,1} + a_2 \int_{c_p} c^{p,2}$ (1.38)

Reversing the orientation of a chain means that integrals over that chain acquire the opposite sign

$\displaystyle \int_{-c_p} c^p = - \int_{c_p} c^p,$ (1.39)

using the set of $ p$ -chains with vector space properties $ C_p({\ensuremath{\mathfrak{K}}}, \mathbb{R})$ , e.g., linear combinations of $ p$ -chains with coefficients in the field $ \mathbb{R}$ . For coefficients in $ \mathbb{R}$ , the operation of integration can be regarded as a bilinear pairing between $ p$ -chains and p-cochains. Furthermore, for reasonable $ p$ -chains and $ p$ -cochains this bilinear pairing for integration is non-degenerate,

$\displaystyle \textnormal{if} \qquad \int_{c_p} c^p = 0 \qquad \forall c_p \in C_p({\ensuremath{\mathfrak{K}}}), \textnormal{then} \; c^p = 0$ (1.40)


$\displaystyle \textnormal{if} \qquad \int_{c_p} c^p = 0 \qquad \forall c^p \in C^p({\ensuremath{\mathfrak{K}}}), \textnormal{then} \; c_p = 0$ (1.41)


... introduced1.2
This map is restricted to simplex cells. A more general mechanism related to the boundary operation is given in Section 1.3.2 and the corresponding practical concept in Section 5.2

next up previous contents
Next: 1.5 Fiber Bundles Up: 1. Mathematical Concepts Previous: 1.3 Topological Toolkit

R. Heinzl: Concepts for Scientific Computing