# Computing Persistent Homology of Directed Flag Complexes
## 4 Materials and Methods
### Performance Considerations
#### 4.4.1 Sorting the Columns of the Coboundary Matrix  
The reduction algorithm iteratively reduces the columns in order of their filtration value (i.e., the filtration value of the simplex that this column represents). Each column is reduced by adding previous (already reduced) columns until the pivot element does not appear as the pivot of any previous column. While reducing all columns the birth and death times for the persistence diagram can be read off: roughly speaking, if a column with a certain filtration value \(f_{0}\) ends up with a pivot that is the same as the pivot of a column with a higher filtration value \(f_{1}\), then this column represents a class that is born at time \(f_{0}\) and dies at time \(f_{1}\). Experiments showed that the order of the columns is crucial for the performance of this reduction algorithm, so [PERSON] sorts the columns that have the same filtration values by an experimentally determined heuristic (see below). This is of course only useful when there are many columns with the same filtration values, for example when taking the trivial filtration where every simplex has the same value. In these cases, however, it can make very costly computations tractable.  
The heuristic to sort the columns is applied as follows:1. Sort columns in ascending order by their filtration value. This is necessary for the algorithm to produce the correct results.
2. Sort columns in ascending order by the number of non-zero entries in the column. This tries to keep the number of new non-zero entries that a reduction with such a column produces small.
3. Sort columns in descending order by the position of the pivot element of the unreduced column. This means that the larger the pivot (i.e., the higher the index of the last non-trivial entry), the lower the index of the column is in the sorted list. The idea behind this is that \"long columns\", i.e., columns whose pivot element has a high index, should be as sparse as possible. Using such a column to reduce the columns to its right is thus more economical. Initial coboundary matrices are typically very sparse. Thus ordering the columns in this way gives more sparse columns with large pivots to be used in the reduction process.
4. Sort columns in descending order by their \"pivot gap\", i.e., by the distance between the pivot and the next nontrivial entry with a smaller row index. A large pivot gap is desirable in case the column is used in reduction of columns to its right, because when using such a column to reduce another column, the added non-trivial entry in the column being reduced appears with a lower index. This may yield fewer reduction steps on average.  
**Remark 1**.: _We tried various heuristics--amongst them different orderings of the above sortings--but the setting above produced by far the best results. Running a genetic algorithm in order to find good combinations and orderings of sorting criteria produced slightly better results on the small examples we trained on, but it did not generalise to bigger examples. It is known that finding the perfect ordering for this type of reduction algorithm is NP-hard [24]._