Numerical instability and computational complexity of the LogLike function

[gvegayon]

After a few tests of the phylo_mcmc function I incidentally realized something that Duncan mentioned some time ago, the complexity of the algorithm is bad. On raw, and perhaps sloppy, terms, as a function of the number of 'functions' -p-, the algorithm performs (p*2^p) computations, ergo, for p = 1, 2, 4 we get

1x2^1 = 2
2x2^2 = 8
4x2^4 = 64

That said, I need to look more carefully to the LogLike function itself, and furthermore, to the probabilities function in C++ to see if we can improve efficiency. This is specially important for the MCMC case.

Here are some tests with the current state of the function:

> benchmark(
+     `1 fun`=with(dat1, LogLike(experiment, offspring, noffspring, c(.2,.2), c(.2,.2), .5)),
+     `2 fun`=with(dat2, LogLike(experiment, offspring, noffspring, c(.2,.2), c(.2,.2), .5)),
+     `3 fun`=with(dat3, LogLike(experiment, offspring, noffspring, c(.2,.2), c(.2,.2), .5)), 
+     replications=100, relative="elapsed")[,1:4]
   test replications elapsed relative
1 1 fun          100   0.005      1.0
2 2 fun          100   0.011      2.2
3 3 fun          100   0.027      5.4

The instability part comes from the fact that, as P increases (and n as well), the size of the rootnode probabilities tend to zero, which is another issue that I encountered throughout the process. That makes the LogLike undefined. Need to take a look on that too.