(This note was originally written by Keenan Crane; at this point all responsibility for content and/or errors lies with Peter Schröder)
When working with surfaces of nontrivial topology, we often need to be able to compute two things: generators for the first homology group, and bases for the space of harmonic \(1\)-forms. Loosely speaking, homology generators represent all the “basic types” of nontrivial loops on a surface. For instance, on a torus we can find two homology generators: a loop going around the inner radius, and a loop going around the outer radius—more generally, a closed surface of genus \(g\) will have \(2g\) generators. Likewise, we will have \(2g\) distinct bases for the harmonic \(1\)-forms, each circulating around a different handle in a different direction (see for example the harmonic component we extracted below via Helmholtz-Hodge decomposition). To get our hands on the harmonic part we will describe an algorithm to find the generators of the first homology of the surface. Such generators are useful for a variety of tasks, for example, cutting open the surface into a single connected component. So there is interest in finding such generators beyond finding harmonic forms. The latter are related to the generators through a simple construction of a suitable \(1\)-form “following” the generator and subsequent Hodge decomposition, as we will see below. But first we discuss finding generators for the first homology of the surface.
Remark: If one is only interested in a basis for the harmonic forms there is a much simpler algorithm to find them. Start with a random \(1\)-form and apply the Hodge decomposition. With high probability there is a non-zero harmonic part. Repeat with another random \(1\)-form. With high probability the harmonic part of that form will be linearly independent of the harmonic part of the first one. Repeat \(2g\) times, orthonormalizing along the way, if you like.
Homology Generators
To find generators for the first homology on a triangulated surface we use the so-called tree-cotree decomposition (“Dynamic Generators of topologically embedded graphs,” “Greedy optimal homotopy and homology generators“). It requires only the most elementary graph algorithms. Here is a quick reminder of some elementary facts about graphs we’ll need. A graph is a set of vertices \(V\) and a collection of edges \(E\) which connect these vertices, i.e., each edge \(e_{ij} \in E\) is an unordered pair \(\{v_i,v_j\}\) of distinct vertices \(v_i,v_j \in V\). For example, the vertices and edges of a simplicial surface describe a graph. At this moment we do not care about orientation, so all edges are unoriented. The faces and dual edges also describe a graph. A subgraph is a subset of a graph that is also a graph. A graph is connected if every vertex can be reached from every other vertex along some sequence of edges. A tree is a connected subgraph containing no cycles. If we wanted to be a bit more geometric (we are studying geometry, after all), we could say that a tree is a simplicial \(1\)-complex that is both connected and simply-connected.
To find a set of generators, we’ll need to compute two spanning trees. A spanning tree is just a tree touching all the vertices of a given graph. How do we compute a spanning tree? If you’ve studied graphs before, you might vaguely recall someone mumbling something like, “Prim’s algorithm… Kruskal’s algorithm… \(O(n \log n)\)…” These two algorithms compute minimal spanning trees, i.e., spanning trees with minimum total edges weight. We don’t care about edge weight, ergo, we don’t care about Prim or Kruskal. Actually, we can use a much simpler linear time algorithm to get a spanning tree:
Algorithm (X-First Search)
Put an arbitrary vertex in a bag, marking it as visited. This first vertex will be the root, which is distinguished by having a parent pointer that is “nil.” Until the bag is empty, pull out a vertex and put all unvisited neighbors in the bag, marking them as visited, and setting their parent pointer to the vertex just pulled out. When the bag is empty all vertices have been visited and for every vertex but the root vertex we have a chain of parent pointers taking us back to the root. This is the vertex spanning tree we seek.
Pretty easy. A “bag” here could be a stack, a queue, or… whatever. In other words, you could do depth-first search. Or breadth-first search. Or anything-first search. The point is, we just need to visit all the vertices. Once we know how to compute a spanning tree, finding a collection of generators on a closed simplicial surface is also easy:
Algorithm (Tree-Cotree)
- Build a spanning tree \(T^\star\) of dual vertices using dual edges, i.e., a spanning tree of all facets.
- Build a spanning tree \(T\) of primal vertices using only primal edges whose dual is not in \(T^\star\).
- The \(2g\) remaining edges which are neither in \(T\) nor having their dual in \(T^\star\) can be used to produce the \(2g\) linearly independent generators we need.
That there are exactly \(2g\) edges left which are neither in \(T\) nor have their dual in \(T^\star\) follows from the Euler characteristic which states\[(|V|-1)+(|F|-1)+2g = |E|\]where the first summand counts the edges in \(T\), while the second summand counts the edges in \(T^\star\).
Exercise: Recall that the fundamental polygon of the torus is just a square with opposite sides glued together. Consider the following graph on the torus:
Run the tree-cotree algorithm by hand, i.e., draw a primal and dual spanning tree on this graph. How many generators did you get? Hint: be careful about corners and edges!
Finally, though we will not show it here, Tree-Cotree will work for surfaces with boundary. In that case there are no dual edges for any primal boundary edge but one. In other words \(T^\star\) must contain (for example: be initialized with) a single dual edge which is dual to one boundary edge. Everything else stays the same (“A fast algorithm to compute cohomology group generators of orientable 2-manifolds“).
So what is so special about these \(2g\) edges that are left over at the end of Tree-Cotree? Consider one such primal edge \([i,j]\). Traversing the tree from \(j\) to the root of the primal spanning tree and concatenating this with the inverse chain from \(i\) to the root and finally the edge \([i,j]\) we have a \(1\)-chain cycle \(\Gamma\). Since none of its edges ever crosses an edge of the dual spanning tree \(T^\star\), we could cut the surface along \(\Gamma\) and the resulting surface would still be connected. This argument can be repeated \(2g\) times. In the end we can create a cell decomposition of the original surface which consists of a single vertex, the root vertex of \(T\), \(2g\) single edges, \(\{e_{\Gamma_i}\}_{i=1\ldots 2g}\) which are the “coalesced” versions of each of the \(2g\) edge loops \(\{\Gamma_i\}_{i=1\ldots 2g}\). Note that each edge \(e_{\Gamma_i}\) begins and ends at the lone root vertex. Consequently \(\partial e_{\Gamma_i}=\emptyset\). Finally there is a single \(4g\)-gon \(2\)-cell. The boundary of this \(2\)-cell is empty as well since each of \(e_{\Gamma_i}\) appears twice, once “forward” (\(+e_{\Gamma_i}\)) and once “backward” (\(-e_{\Gamma_i}\)) traversed. For example, in the case of the torus we get a \(4\)-gon with opposite edges identified and the four corners corresponding to a single “root” vertex on the torus.
Given that the first homology of the surface is the quotient of \(\textrm{ker}(\partial_1)=\) and \(\textrm{im}(\partial_2)\) we can write it explicitly as\[H_1=\frac{\textrm{ker}(\partial_1)}{\textrm{Im}(\partial_2)} = \frac{\textrm{span}(\{\Gamma_i\}_{i=1\ldots 2g})}{\emptyset}=\textrm{span}(\{\Gamma_i\}_{i=1\ldots 2g}).\]
Harmonic Bases
Once we have the homology generators, the harmonic 1-form bases can also be found using a rather simple procedure (“Designing Quadrangulations with Discrete Harmonic Forms“). In fact, we can take advantage of our newly-acquired knowledge of Hodge decomposition. Suppose we start out with a 1-form \(\omega\) that is closed but not exact, then it must be of the form\[\omega = d\alpha + h\]for some 0-form \(\alpha\) and harmonic 1-form \(h\). Using our procedure for Helmholtz-Hodge decomposition we can easily extract just the harmonic part. In fact, since \(\omega\) has no coexact component we need only solve \(\delta d\alpha = \delta \omega\), or equivalently\[-\Delta\alpha = \delta\omega.\]In other words, just a standard scalar Poisson equation. We can then extract the harmonic component via \( h = \omega – d\alpha \) as before.
Sounds pretty good, but where did \(\omega\) come from in the first place? In other words, how do we construct a \(1\)-form that is closed but not exact? For this purpose we will use a dual cycle. Given one of the \(2g\) edges which are neither in \(T\) nor their dual in \(T^\star\), take its dual and use the dual chains up to the root of \(T^\star\) to construct a \(2\)-chain cycle on the surface. Now we will create a primal \(1\)-form \(\omega\) as follows. For every primal edge crossing from the “left” of the dual cycle to the “right,” set \(\omega\) to \(+1\); for every primal edge crossing from the “right” to the “left,” set \(\omega\) to \(-1\):
For all remaining edges, set \(\omega\) to zero. The resulting \(1\)-form is closed. Why? Well, remember that the discrete exterior derviative on \(1\)-forms is just the (oriented) sum of edge values around each triangle. Therefore, in each triangle crossed by our dual generator, we get \(1-1+0=0\):
(In all other triangles we get \(0+0+0=0\).) Ok, so this particular choice of \(\omega\) is closed. But is it also exact?
Exercise: Show that the \(1\)-form \(\omega\) described above is not exact, i.e., it has a nonzero harmonic component. Hint: Stokes’ theorem!
Exercise: Let \(\Gamma_1,\ldots,\Gamma_{2g}\) be a collection of homology generators, constructed as described earlier. Let \(\omega_1,\ldots,\omega_{2g}\) be the corresponding closed 1-forms, and let \(h_1,\ldots,h_{2g}\) be the corresponding harmonic components. Show that the \(h_i\) are linearly independent.
Algorithm (Harmonic-Basis)
Compute homology generators \(\Gamma_1\ldots\Gamma_{2g}\) using Tree-Cotree.
for \(i=1,\ldots,2g\)
- Construct a closed \(1\)-form \(\omega_i\) corresponding to \(\Gamma_i\).
- Solve \(-\Delta\alpha_i = \delta\omega_i\).
- \(h_i \leftarrow \omega_i – d\alpha_i\)
endfor
As discussed in the chapter on parameterization, we can greatly accelerate the process by prefactoring the Laplace operator. Since the cost of prefactorization is typically far greater than the cost of backsubstitution (and since Tree-Cotree amounts to a simple linear traversal), the overall cost of this algorithm is roughly the same as the cost of solving a single Poisson equation.
Exercise: Above we constructed \(\omega_i\) by using a dual cycle generated by a dual edge in the set of \(2g\) generator “seeds” and the dual tree \(T^\star\). Show that we can just as well use a primal cycle generated by the primal edge in the set of \(2g\) generator “seeds” and the primal tree \(T\). Again we must design a suitable \(\omega_i\). Give an assignment of values to primal edges so that \(\omega_i\) is co-closed. A suitably chosen Hodge decomposition and associated Poisson problem will then give a corresponding \(h_i\) which is harmonic. Spell out the details. Hint: a primal \(1\)-chain connects dual (to the primal vertices) 2-cells.
