appliedtopology – Page 38 – Applied Topology

Speeding up Homology via Duality?

In the last post I constructed for any (locally finite) simplicial complex a dual complex. Today, I thought of using this to gain a potential speed-up in computational homology. Note that simplicial homology of is the same as Cech homology of the cover given by open stars of the vertices of . This is because … Continue reading →

In the last post I constructed for any (locally finite) simplicial complex $K$ a dual complex. Today, I thought of using this to gain a potential speed-up in computational homology.

Note that simplicial homology of $K$ is the same as Cech homology of the cover given by open stars of the vertices of $K$ . This is because the nerve of this cover is precisely $K$ and Cech homology is not-so-secretly the simplicial homology of the nerve.

However, we know that the dual complex has the same homotopy type as $K$ , but the number of vertices in the dual complex is equal to the number of maximal simplices. Simplicial homology of this dual complex is the same as Cech homology of the cover given by the closed top dimensional cells in $K$ .

Here is a case where this observation results in a most dramatic speed-up. The standard n-simplex $\Delta^n$ has $2^{n+1}$ simplices and naively simplicial homology requires storing all of these. However, the dual complex is a single point and Cech homology here reveals that. Thus we have gone from a chain complex with $n+1$ chain groups, each of which are dimension $\binom{n+1}{j}$ to a chain complex concentrated in a single degree, all by using this duality.

Of course, the case of graphs shows where this duality fails miserably. The dual complex creates simplices whose dimension corresponds to the degree of vertices in the original graph, so we can go from a two-term chain complex with a single boundary matrix, to arbitrarily large chain complexes.

This presents a question of possible interest: For what simplicial complexes does the dual complex and the original complex have the same number of simplices? ~~Triangulated manifolds clearly do, but what about other simplicial complexes?~~ Can we say something about the expected discrepancy of these numbers?

Dual Simplicial Complexes

In the process of designing homework problems for Applied Algebraic Topology (ESE 680-003) last night, I stumbled upon a most beautiful application of the nerve theorem as well as a construction of a dual simplicial complex that is defined for any (locally finite) simplicial complex . This dual complex has the property that it is … Continue reading →

In the process of designing homework problems for Applied Algebraic Topology (ESE 680-003) last night, I stumbled upon a most beautiful application of the nerve theorem as well as a construction of a dual simplicial complex that is defined for any (locally finite) simplicial complex $K$ . This dual complex has the property that it is always homotopic to the original simplicial complex.

Let $K$ be a simplicial complex with vertex set $V$ . The open star $U_v$ of a vertex $v$ is defined to be the set of simplices $\sigma$ containing $v$ . Visibly, the nerve of the cover $\mathcal{U}=\{U_v | v\in V\}$ is the same as the simplicial complex $K$ .

On the other hand, one can consider a different cover by closed sets, or dually Alexandrov opens when one reverses the partial order. Define a simplex to be maximal if it is not the face of any other simplex. Define the closure $\overline{\sigma}$ of a simplex $\sigma$ to be the set of faces of $\sigma$ , written $\tau\leq\sigma$ , so that $\sigma\leq\sigma$ , i.e. $\sigma$ is a face of itself.

Now define the dual simplicial complex of $K$ to be the nerve of the cover $\mathcal{V}=\{\overline{\sigma} | \sigma \,\mathrm{maximal}\,\}$ .

The nerve theorem works for convex closed sets or open sets with contractible intersections, so we know this dual simplicial complex has to be homotopy equivalent to the simplicial complex $K$ .

If we use Graeme Segal’s construction of the classifying space of the cover category $X_U$ (sometimes called the Mayer-Vietoris blowup complex) in the paper “Classifying Spaces and Spectral Sequences” then we should be able to construct a similar dual space for cell complexes by looking at the open stars of vertices and the closures of maximal cells respectively.

Exact sequence of a pair: Computing the connecting map

Given a pair of spaces , with , the short exact sequence of the pair is a relationship between the chains and . The sequence that looks like this: (1) is short exact, or that: . If you want to know more about exact sequences I recommend reading this. It turns out that on […]

Given a pair of spaces $(X,A)$ , with $A \subset X$ , the short exact sequence of the pair is a relationship between the chains $C_*(A),C_*(X/A)$ and $C_*(X)$ . The sequence that looks like this:

(1) $\begin{equation*} 0 \longrightarrow C_*(A) \xlongrightarrow{i} C_*(X) \xlongrightarrow{j} C_*(X/A) \longrightarrow 0 \end{equation*}$

is short exact, or that: $\Ker{j} = \Im{i}$ . If you want to know more about exact sequences I recommend reading this.

It turns out that on the level of homology this short exact sequence turns into a long exact sequence:

(2) $\begin{equation*} \ldots \longrightarrow H_*(A) \xlongrightarrow{i_*} H_*(X) \xlongrightarrow{j_*} H_*(X/A) \xlongrightarrow{\delta} H_{*-1}(A) \ldots \end{equation*}$

and the map $\delta$ is called the connecting homomorphism.

The natural question to ask is: What is $\delta([x])$ ? The answer is that
that $\delta([x]) = [\partial[x]]$ . However, if you read the aforementioned authoritative text on the subject you will see that $\delta$ is not explicitly defined, but its existence is merely proved.

However, given a particular $X$ and $A$ , one is able to come up with an idea of what the map does. I’ll go over the basic diagram chase and then show how this works by example.

Since we are given a representation of $H_*(X/A)$ we can begin by taking a homology class $\hat{c}$ which is relative cycle. Any chain $c$ in $X$ which is in the class $\hat{c}$ has the property that $j(c) = \hat{c}$ in $H_*(X/A)$ . Such a chain $c$ is called a lift.

Assuming we have found a lift we can compute $z = \partial(c)$ , and it turns out that $z \in Z_{*-1}(A)$ (because $\partial{j} = j\partial$ ), which means that $[z] \in H_{*-1}(A)$ . So our mapping sends $\hat{c} \in H_*(X/A)$ to $[z] \in H_{*-1}(A)$ . So you now just need to prove that this process is well defined and this ends your diagram chase as well as your interest in the details of this sequence. Unless of course you are Mr. Cooperman, or, a computer scientist.

If you are a computer scientist you might be dissatisfied because it is not entirely clear how $[z]$ is presented. Indeed $z$ itself is not unique as it depends on our choice of lift, $z$ is likely itself not even a member of our given representative for homology on $H_{*-1}(A)$ .

The problem we have is that so far our cycle $z$ is written down as a linear combination of cells. We want an equivalent representation in terms of cycles. Noether says we can write down $Z_{*}(A) \simeq H_{*}(A) \oplus B_{*}(A)$ .
This tells us that we can use our homology basis to form a basis for our cycle group, and its not to hard to see that we can extend the cycle group to a basis for all chains. However in our case we want to take a cycle expressed in the chain basis, and write it as a linear combination of given cycles. This amounts to being able to write down a rectangular “change of basis” matrix between the cell basis and the given cycle basis on $Z_{*-1}(A)$ .

The column space of this matrix would be given by our given cycle basis, and the row space would be given by the canonical cell basis for $C_{*-1}(A)$ . We then look to “solve $Ax = z$ ” over $\mathbb{Z}_p$ (in this blog $p = 2$ ), in the sense that we want to write down a linear combination of the cycles in $Z_{*-1}(A)$ apply our matrix and end up with the $z$ we computed.

Consider this space $A$ :

Rendered by QuickLaTeX.com

which is homotopic to an annulus.

We can imagine that $A \subset X$ , and that $X$ is obtained by gluing a disc onto the boundary of $A$ , so that $X$ is itself homotopic to a disc, $X/A$ is then homotopic to a sphere, with exactly one non-trivial 2nd homology class. The boundary of this class would be the outermost cycle of $A$ .

Lets say that we are provided a basis for $H_1(A) = \langle \alpha = bc + cd + db \rangle$ and $B_1 = \langle \beta = ab + bc + ca \rangle$ . If I want to express the outer bounding cycle $ab + bd + dc +ca$ in this basis, I begin by writing down the change of basis matrix, in order to solve $Ax=z$ I augment the matrix with the identity matrix on the right and $z$ on the bottom.

$A' = \left( \begin{array}{c|ccccc|cc} & ab & ac & bc & bd & cd & \alpha & \beta \\ \hline \alpha & 0 & 0 & 1 & 1 & 1 & 1 & 0 \\ \beta & 1 & 1 & 1 & 0 & 0 & 0 & 1 \\ \hline & 1 & 1 & 0 & 1 & 1 & 0 & 0 \end{array} \right)$

Now you can see that modulo our extra row for $z$ our matrix is in row echelon form, and it suffices to perform one Gaussian elimination (over $Z_2$ ) in this last column to achieve our result:

$\left( \begin{array}{c|ccccc|cc} & ab & ac & bc & bd & cd & \alpha & \beta \\ \hline \alpha & 0 & 0 & 1 & 1 & 1 & 1 & 0 \\ \beta & 1 & 1 & 1 & 0 & 0 & 0 & 1 \\ \hline z & 1 & 1 & 0 & 1 & 1 & 0 & 0 \end{array} \right)$

$z \rightarrow z + \beta$

$\left( \begin{array}{c|ccccc|cc} & ab & ac & bc & bd & cd & \alpha & \beta \\ \hline \alpha & 0 & 0 & 1 & 1 & 1 & 1 & 0 \\ \beta & 1 & 1 & 1 & 0 & 0 & 0 & 1 \\ \hline z=\beta & 0 & 0 & 1 & 1 & 1 & 0 & 1 \end{array} \right)$

$z \rightarrow z + \alpha$

$\left( \begin{array}{c|ccccc|cc} & ab & ac & bc & bd & cd & \alpha & \beta \\ \hline \alpha & 0 & 0 & 1 & 1 & 1 & 1 & 0 \\ \beta & 1 & 1 & 1 & 0 & 0 & 0 & 1 \\ \hline z=\alpha+\beta & 0 & 0 & 0 & 0 & 0 & 1 & 1 \end{array} \right)$

Notice how the right hand side now contains our vector $x$ and indeed $Ax = z = \partial(j(c))$ .