UnionFind icon indicating copy to clipboard operation
UnionFind copied to clipboard

Runtime scaling is not linear for a large lattice

Open chaeyeunpark opened this issue 4 years ago • 3 comments

Simulation results up to 127x127x127 lattice show that the scaling is not linear. Need to profile (does the greedy implementation of the minimum spanning tree slow down it?)

uf_3d_timing

chaeyeunpark avatar Jun 15 '21 18:06 chaeyeunpark

why is it necessary to implement minimum spanning tree, from the paper https://arxiv.org/abs/1703.01517 peeling algorithm only need spanning tree, which can be implemented in O(n). Maybe I misunderstand your needs for MST?

Qi-Zhan avatar May 14 '22 08:05 Qi-Zhan

Hi @Qi-Zhan, thank you for the question! I don't know why I wrote that. The current algorithm the implementation uses is O(n). Still, there might be a slight deviation from the linear scaling if the size of the lattice becomes too huge. It may be from a hash map implementation rather than the algorithm side.

chaeyeunpark avatar May 14 '22 13:05 chaeyeunpark

Hi, thank you for answer. I guess it is beacause of some implementation, too.

Qi-Zhan avatar May 15 '22 02:05 Qi-Zhan