35
$\begingroup$

I refer to this paper: de Silva, Vin; Morozov, Dmitriy; Vejdemo-Johansson, Mikael. Dualities in persistent (co)homology. Inverse Problems 27 (2011), no. 12, 124003, 17 pp. (Journal link, arXiv link).

According to the results in the paper, especially the experiments in page 15 it shows that persistent cohomology is faster than persistent homology by a factor of around 30 to 50.

That seems quite amazing to me, considering that over fields, homology and cohomology are dual. The paper does explain the reason why, but I don't really get the key idea how it accounts for a 3000% to 5000% improvement over persistent homology.

The paper's explanation (also on pg 15) is based on the difference between row operations and column operations. Apparently, row operation is supposed to be the better one, and since persistent cohomology can use the row operation (while it is difficult for homology), it results in better results. Also, the column algorithm (the worse algorithm) has to store all dead cycles, while for the row algorithm we can delete those cycles that died.

Also, theoretically, I am curious if such wonderful optimizations can be done for persistent cohomology, why can't the same be done for the dual persistent homology? Is there any theoretical reason for the impediment in persistent homology algorithms? Ideally I would imagine that the "best persistent cohomology algorithm" would perform as well as the "best persistent homology algorithm".

Thanks for any enlightenment.

$\endgroup$
1
  • 12
    $\begingroup$ The difference in efficacy is not in computing the barcode (which is the same for homology and cohomology, as mentioned in the paper) but in computing the (co)cycles which generate the (co)homology. So even though we have an isomorphism between barcodes, there is no canonical isomorphism. $\endgroup$ Jan 8, 2018 at 17:49

1 Answer 1

31
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.