# Merging Discrete Morse Vector Fields: A Case of Stubborn Geometric Parallelization
## 2 Discrete Gradient Vector Fields
To give an ordering to higher dimensional cells, a new function, \(G\), is introduced, defined as follows: if \(\sigma\) contains the vertices \(\{x,y_{1},\cdots,y_{n}\}\), then \(G(\sigma)=\{g(x),g(y_{i_{1}}),\cdots,g(y_{i_{n}})\}\), where \(g(x)>g(y_{i_{1}})>\cdots>g(y_{i_{n}})\). This allows us to impose the lexicographical ordering on \(G\) when performing this algorithm. The algorithm, itself, then takes all of the cells of \(L(x)\) and either possibly pair a cell, \(\tau\), with a codimensional \(1\) face, \(\sigma\), and place them \((\sigma\leq\tau)\) in \(V\), or take a cell, \(\sigma\), and place it singly in \(C\) in the following way:  
* If \(L(x)=\{x\}\), then \(x\in C\). Otherwise, take the minimal (with respect to \(G\)) \(1\)-cell, \(\tau\), and \((x\leq\tau)\in V\). All other \(1\)-cells are added to a queue called PQzero since they have no remaining unpaired faces in \(L(x)\). All cofaces of codimension \(1\) of \(\tau\) in \(L(x)\) that have \(1\) unpaired face in \(L(x)\) are added to a different queue called PQone. * The algorithm then takes the minimal cell (with respect to \(G\)) that is in PQone and either moves it to PQzero, if it has no unpaired faces remaining in \(L(x)\). If it still has an unpaired face, it gets paired with that face and is put into \(V\). Then we look at all cofaces of codimension \(1\) of both cells that were just paired and put into \(V\). If any of these cofaces have exactly one unpaired face, they are added to the queue PQone. * Then, if PQzero is not empty, it takes the minimal cell (with respect to \(G\)), called \(\delta\), and places it singly in \(C\). Then all cofaces of codimension \(1\) of \(\delta\) are inspected. If any these cofaces have exactly one unpaired face, it is placed in PQone. This keeps going until both PQzero and PQone are empty. Note that in particular, \(L(x)=x[1]\), using the notation defined above. ProcessLowerStars, in fact, only looks at \(\sigma[1]\), where \(\sigma\) is a \(0\)-cell. We present a simple example in Figure 1 with \(V_{\alpha}(K)\
eq V_{\alpha}(U)\cup V_{\alpha}(W)\), where \(\alpha\) is the ProcessLowerStars algorithm from [2] and \(U\) and \(W\) are subcomplexes of \(K\) such that \(K=U\cup W\). Let \(K\) be the following \(1\)-dimensional cubical complex with the function values, \(f\), on the \(0\)-cells. First, we apply \(\alpha\) to all of \(K\). This gives \(V_{\alpha}(K)=\{\{3,31\},\{4,42\}\}\). Next, we break up \(K\) into the following subcomplexes: \(U=\{1,3,4,31,43\}\) and \(W=\{2,3,4,43,42\}\). When we apply \(\alpha\) to \(U\), we obtain \(V_{\alpha}(U)=\{\{3,31\},\{4,43\}\}\). When we apply \(\alpha\) to \(W\), we get \(V_{\alpha}(W)=\{\{4,42\}\}\). Clearly, \(V_{\alpha}(K)\
eq V_{\alpha}(U)\cup V_{\alpha}(W)\), so simply merging the lists from the subcomplexes does not give us the correct discrete vector field for all of \(K\). In this particular instance, we obtain an extra pairing, the \(\{4,43\}\) from \(U\). The failure of naive merging is made clearer using the following definition and explanation. Let \(\sigma_{C}[k]\) be the \(k\)-star of \(\sigma\) viewed as a cell within the subcomplex \(C\) of \(K\). This is intrinsic to the \(C\) construction and so may differ from \(\sigma[k]\), which is the same as \(\sigma_{K}[k]\), for some combinations of \(\sigma\) and \(k\). Since the algorithm \(\alpha\) takes as input the data from \(\sigma_{C}[k]\), there are cases when the discrepancy leads to different constructions of the vector fields as Example 2 shows. This also points to some cases when this discrepancy does not happen. Suppose \(K\) is a disjoint union of subcomplexes \(C_{i}\), for \(i\) from some index set \(I\). In other words, a connected subset of \(K\) is contained entirely within one and only one \(C_{i}\). Then \(V_{\alpha}(K)=\bigcup_{i\in I}V_{\alpha}(C_{i})\). Proof. : For every pair \((\sigma\leq\tau)\), its inclusion in \(V_{\alpha}(C_{i})\) is decided by \(\alpha\) from the data within \(\sigma_{C_{i}}[k]\).