search

Ripser / ripser

Ripser: efficient computation of Vietoris–Rips persistence barcodes
http://ripser.org
MIT License
311 stars 78 forks source link

Some Distance Matrices Grind Ripser To A Halt #14

Closed ctralie closed 6 years ago

ctralie commented 6 years ago

Hi Uli, I'm attaching a distance matrix which seems to grind Ripser to a halt, even though I'm only doing H1 on 179 points. GUDHI processes it just fine.

./ripser D.txt

D.txt

ctralie commented 6 years ago

For some context, this comes from some points arranged on a loop in very high dimensions, with noise added so that the points all spread out very far apart. But even if you do PCA down to two dimensions, you'll see a loop dslow

ubauer commented 6 years ago

Hi Chris,

thanks for sending the example! In the current release, Ripser by default uses a way of computing persistence that uses a bit less memory and typically runs a bit faster than the "usual" matrix reduction algorithm, but there are some instances where it might be much slower. Previously I haven't seen many such instances in practice, but sometimes they show up. To be on the safe side, in the next release I will change the default to the usual matrix reduction (the option is ASSEMBLE_REDUCTION_MATRIX).

With the current version, you can run the binary "ripser_reduction", which has ASSEMBLE_REDUCTION_MATRIX enabled. This one is fast for your data set (takes about one second for H^1).

ctralie commented 6 years ago

Hi Uli, Thank you for the lighting fast response! That does indeed fix it. Thanks, Chris

ctralie commented 6 years ago

P.S. Do you have a writeup about this yet? It would love to understand more what you're doing. Also, I've been citing ripser everywhere to the best of my ability, for instance, reference 3 here:

https://arxiv.org/pdf/1704.08382.pdf

but I want to make sure for your sake that this is actually getting the Google Scholar juice it deserves