This week I have spent huge amounts of time attempting to escape the gravity well of the multimatching work, and finally, it has paid off. The multimatching algorithm is now working for all algorithms (multilevel, octree and MGF) and my experiments have been started. I should have results by Monday, and am currently writing up the technical report to accompany the work.
So finally, I have made some progress - and what a feeling it is.
Currently there is nothing else worth mentioning and as it's a Saturday, I want to get back to my precious games, so for now, that's all. Stay tuned for The Results Return, where our protagonist identifies the unlikeliest of issues, and fights for his sanity so he can return to the glorious path of Progression.
Have a good weekend!
Saturday, 16 June 2012
Friday, 8 June 2012
EGH2012 Workshop
So remember how I dislike talking in front of crowds of people? Turns out mathematicians aren't people, theyre cruel questioning machines who seem to know everything about the universe. Why do I say this/bring this up? Well I had the great fortune of being included in the EGH2012 Workshop right here at the University of Greenwich, and was allowed to give a short 10minute exposition of my research.
Although I wasn't ridiculed, I feel I could have done better regarding my explanation of some aspects (such as the forces involved and their importance, and more about my intent regarding dynamic graphs). I was only faced with one question regarding multipole techniques, which was relatively easy to answer - but I am bias by not being able to "see" what I said (what I think I said and how it came out may differ...).
However pessimistic I can be, it was still good practice for talking in front of an audience - even more so for an audience unfamiliar with such a topic. Moving on from the horrors, I am continuing with the issues of the multimatching layouts, with a hope of finishing this by next week (by may mean by Friday next week, but we will see how progress goes over the weekend).
A rather short update for now, mostly due to my attendance of the EGH2012 workshop but also due to the lack of progression of my research. On the bright side, I have been preparing some notes regarding my implementation of the MGF tree in a dynamic enviroment to reduce the time required to respond to changes. For now, thats all folks, have a good weekend.
Although I wasn't ridiculed, I feel I could have done better regarding my explanation of some aspects (such as the forces involved and their importance, and more about my intent regarding dynamic graphs). I was only faced with one question regarding multipole techniques, which was relatively easy to answer - but I am bias by not being able to "see" what I said (what I think I said and how it came out may differ...).
However pessimistic I can be, it was still good practice for talking in front of an audience - even more so for an audience unfamiliar with such a topic. Moving on from the horrors, I am continuing with the issues of the multimatching layouts, with a hope of finishing this by next week (by may mean by Friday next week, but we will see how progress goes over the weekend).
A rather short update for now, mostly due to my attendance of the EGH2012 workshop but also due to the lack of progression of my research. On the bright side, I have been preparing some notes regarding my implementation of the MGF tree in a dynamic enviroment to reduce the time required to respond to changes. For now, thats all folks, have a good weekend.
Friday, 1 June 2012
Foolish Mistakes
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!
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!
Subscribe to:
Posts (Atom)