Accelerating GPCCA

[Marius1311]

The current bottleneck for msmtools/GPCCA is the optimisation, see msmdev/msmtools#7. There are two ways to tackle this:

1. speed up the _fill_matrix routine. This approach should be relatively straight forward and can be done in the short- to medium time frame
2. replace the Nelder-Mead optimizer with a Gauss-Newton optimiser. There is a matlab implementation for this, it just has to be ported to Python correctly. As it stands, see Scaling - optimization potential msmdev/msmtools#7, this involves a bit more work, so this is a medium to long time frame task.

[michalk8]

Not sure why _fill_matrix scales the way it does, will look into it. I'd leave 2. for Bernhard, since he has the necessary knowledge to do it properly.

[michalk8]

I've tried accelerating it with numba, but the main issue is that it's being called many times in the optimization method.
Here are the results

# mean (s), var (s) - per function call
(0.0010434131756720828, 1.1502677893982577e-06) # original
(0.0008908883376944168, 1.3730149499314552e-06) # jit
(0.0008944822371139355, 1.9075765642422098e-06) # jit with parallel max

[Marius1311]

Thanks for looking into it. The change per function call is tiny, but just to be sure this is not a promising approach for compute time optimisation, could you look at the overall computation time spend in the _fill_matix function on an example case (take the pancreas, compute m=10 states) once with numba, once without?

[michalk8]

I've look at the whoe runtime, it's negligible decrease:

278 ms ± 5.74 ms per loop (mean ± std. dev. of 7 runs, 20 loops each)  # without numba
275 ms ± 9.43 ms per loop (mean ± std. dev. of 7 runs, 20 loops each)  # with numba

[Marius1311]

okay, you're right, that's not significant. The way to go would be to change the optimization then. Let's leave this for later.

[Marius1311]

This actually shouldnt' be too difficult @michalk8 . Could you have a look in the matlab implementation please and let me know how much effort you estimate this would be?

[Marius1311]

This is already implemented in Matlab, we just need to port it.

[michalk8]

@Marius1311 how hard would this be?

[Marius1311]

ah Bernhard mentioned there may be a couple of tricky special cases so I suspect it may take somewhat longer.