There are several factors contributing to the improved performance of the algorithm reported in the paper; the use of cohomology is one, but there is also a computational shortcut involved, and the top Betti number (more precisely, the dth Betti number of the (d+1)-skeleton) also plays a role.
The computation of persistence barcodes is based on a variant of Gaussian elimination, applied to the columns of the boundary matrix of a filtered chain complex. Since the filtration order is important, no columns are exchanged, and eliminations are only done using left-to-right column additions. Gaussian elimination does not make use of the fact that the matrix is a boundary matrix. But this fact can be exploited to take a significant shortcut in the matrix reduction.
This shortcut, called the “clearing” optimization, allows one to clear out entire columns at once. The shortcut has been found independently by Chao and Kerber as well as by Morozov et al. (its use is implicit in the description of the cohomology algorithm of the mentioned paper). Clearing applies to both the homological and cohomological versions of barcode computation. In the mentioned paper, the cohomology algorithm uses clearing, while the homology algorithm does not.
The experimental results of the paper thus tell us that persistent cohomology with clearing is faster than persistent homology without clearing. As it turns out, however, cohomology with clearing is also faster than homology with clearing on typical examples, clarifying the role of cohomology for computational purposes.
Applying clearing requires performing the column operations in an appropriate order. For homology, clearing the column of a q-simplex requires reducing the column of a (q+1)-simplex first. In cohomology, in contrast, clearing the column of a q-simplex requires reducing the column of a (q-1)-simplex first.
If the goal is to compute persistence barcodes only up to a certain homological degree d, the computation starts with reducing columns of (d+1)-simplices. For those columns, clearing is not available. The number of columns that will be reduced to a zero column is exactly the
(d+1)st Betti number of the (d+1)-skeleton.
Now especially when computing persistence for Vietoris–Rips filtrations, the degree d is typically chosen small, and there are a lot more (d+1)-simplices than simplices of lower dimension, and also the (d+1)st Betti number will be large. When computing persistent homology, clearing only zeroes out columns of lower-dimensional simplices, and so the speedup obtained might be quite small. On the other hand, for cohomology, clearing is unavailable only for 0-simplices, but the number of 0-simplices is small, and persistence in dimension 0 can be computed very quickly using a union-find data structure instead.
In summary: clearing speeds up the computation of persistence, and cohomology typically allows for more clearing than homology, especially in the case of Vietoris–Rips filtrations.
