I am curious whether it is significantly harder (computational-wise) to compute persistent homology as compared to computing homology. Or is it the same time complexity.

I am aware that there is a reduction algorithm for homology. I vaguely recall that it has polynomial complexity, though I can't find the reference now. I would be grateful if someone can point me to any reference.

From the description of persistent homology, it is clear that it can't be easier than computing homology. But for computing one homology group, say $H_n(X)$, vs computing one persistent homology group, say $H_n^{i,p}$, I am not sure which is easier. By Carlsson's theory, persistent homology is the same as the usual homology of a graded module, hence I am not sure if this implies that the complexity is the same as computing homology.

Thanks for any help. Any references will be greatly appreciated.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.