Is there a faster algorithm for computing fastFloyd?

[hhxy03]

As tested in different size of input matrix, profiling the running time of function fastFloyd,
I found that its time complexity is extremely high at about O(n^5).

Here is the test result

matrix size	running time
1000 * 1000	5s
2000 * 2000	126s
3000 * 3000	1000s

So if I want to boost the Hi-C data in chromosome 1, It nearly costs 80 hours.

Is there anyway to accelerate this function, parallelizing or writing in C?

[LeopoldC]

Hey, there is several way to optimize the FloydWashall algorithm:
-maybe this one is a good option https://www.ijarse.com/images/fullpdf/1371224241_SHORTEST_PATH_USING_NEURAL_NETWORK.pdf

-this other repository seems to be good start, just need to optimize it for this specific case issue and win a x2 ratio.
https://github.com/mosco/floyd-warshall-cython

Unfortunately, I never had the time to test and implement those kind of option for now.

If you need fast result, I'm always run boost hic by centromeric arm on human dataset, for compartment result seems to be nice like this. It's depending of what you need.
If you want to run boost hic only once, I advise you an alpha close to 0.2 by default