As expected, there is only one explanation for every error that occurs in my applications - me. It seems once again, the massive increase in runtime was my fault and down to the smallest mistake known to mankind - using the wrong information.
As identified time and time again, the issue was coming from the calculation of repulsive forces, where it spent more time than it should have (4000ms instead of 900ms for 3elt, for example). At first, this looked to be the tree, which after some difficulty and work, was ruled out. The structure of the approximation/coarsening tree was as expected.
It was then hypothesised that more time was spent converging to a nice layout, but once again, a comparison of the number of times each algorithm run showed no difference. When coupled with the tree structure being correct, this didnt make much sense.
To aid in finding the issue, I had friends/fellow programmers (the whole of 2 people!) check over my code and try to identify the changes from previous implementations. This came up with many causes which were ruled out, but came to the conclusion that it was something I had assumed in the algorithm which was incorrect.
Finally, outputting every possible computation at every stage identified the problem. Instead of using the matching tree to approximate forces, the application was using the list of adjacent vertices. This caused the number of calculations to increase to a function of the average degree within the graph (as opposed to a lower number given by the matching number - in this case 2 or 3).
Fixing this has identified some other issues which are currently being investigated, but thankfully, I can now finished the implementation, move onto the testing/experimentation and finish this. I shall update again next week with a small progress update.
Have an enjoyable 4-day weekend!
No comments:
Post a Comment