# Computing Persistent Homology of Directed Flag Complexes
## 4 Materials and Methods
### Computing the Coboundaries  
In Ripser, [10], cohomology is computed instead of homology. The reason for this choice is that for typical examples, the coboundary matrix contains many more columns that can be skipped in the reduction algorithm than the boundary matrix [23].  
If \(\sigma\) is a simplex in a complex \(X\), then \(\sigma\) is a canonical basis element in the chain complex for \(X\) with coefficients in the field \(\mathbb{F}\). The hom-dual \(\sigma^{*}\), i.e., the function that associates \(1\in\mathbb{F}\) with \(\sigma\) and \(0\) with any other simplex, is a basis element in the cochain complex computing the cohomology of \(X\) with coefficients in \(\mathbb{F}\). The differential in the cochain complex requires considering the coboundary simplices of any given simplex, i.e., all those simplices that contain the original simplex as a face of codimension 1.  
In Ripser, the coboundary simplices are never stored in memory. Instead, the software enumerates the coboundary simplices of any given simplex by a clever indexing technique, omitting all coboundary simplices that are not contained in the complex defined by the filtration stage being computed. However, this technique only works if the number of theoretically possible coboundary entries is sufficiently small. In the directed situation, and when working with a directed graph with a large number of vertices, this number is typically too large to be enumerated by a 64-bit integer. Therefore, in Flagser we pre-compute the coboundary simplices into a sparse matrix, achieving fast coboundary iteration at the expense of longer initialisation time and more memory load. An advantage of this technique is that the computation of the coboundary matrices can be fully parallelised, again splitting the simplices into groups indexed by their initial vertex.  
Given an ordered list of vertex identifiers \((v_{0},\ldots,v_{k})\) characterising a directed simplex \(\sigma\), the list of its coboundary simplices is computed by enumerating all possible ways of inserting a new vertex into this list to create a simplex in the coboundary of \(\sigma\). Given a position \(0\leq p\leq k+1\), the set of vertices that could be inserted in that position is given by the intersection of the set of vertices that have a connection from each of the vertices \(v_{0},\ldots,v_{p-1}\) and the set of vertices that have a connection to each of the vertices \(v_{p},\ldots,v_{k}\). This intersection can again be efficiently computed by bitwise logical operations of the rows of the adjacency matrix and its transpose (the transpose is necessary to efficiently compute the incoming connections of a given vertex).  
With the procedure described above, we can compute the coboundary of every \(k\)-simplex. The simplices in this representation of the coboundary are given by their ordered list of vertices, and if we want to turn this into a coboundary matrix we have to assign consecutive numbers to the simplices of the different dimensions. We do this by creating a hash map, giving all simplices of a fixed dimension consecutive numbers starting at 0. This numbering corresponds to choosing the basis of our chain complex by fixing the ordering, and using the hash map we can lookup the number of each simplex in that ordering. This allows us to turn the coboundary information computed above into a matrix representation. If the flag complex is stored in memory, creating a hash map becomes unnecessary since we can use the complex as a hash map directly, adding the dimension-wise consecutive identifiers as additional information to each simplex. This eliminates the lengthy process of hashing all simplices and is therefore useful in situations where memory is not an issue.