Is this even my code?

This week I have been continuing with the coding of the multi-matching which, as mentioned before, is becoming a more prominent pain than it should be. As this is similar to my previous implementation, and much of the code pasted across, it is difficult to identify which part of the previous algorithm should be saved and which should not.

Unfortunately there is not much else to update upon at this time, unless you like reading my complaints about my own work... Regardless, any timeline/plan I set for this seemingly simple task gets completely ignored, so for now, I will set one for the end of June (because a stupidly large amount of time should be enough, right?). I will look to have everything finished, with the possible exception of the testing, by then so I can begin the long awaited dynamic work.

Paper Submission and Matching Hells

This week started well with my start on re-arranging the Information Visualisation 2012 conference paper to match the required style of the IEEE publishing template (in what can now be called the most irritating activity of all time). This continued until yesterday evening, with both conference paper and proceedings having been submitted successfully, and with registration and arrangement of travel and accommodation underway (not that I have much to do with that).

From today onwards, I have been working to resolve the big difference in runtimes between the previous edge contraction implementation, and the multimatching. Unfortunately, this is harder to fix than previously expected, but as I continue to work on it, other ideas/issues come to mind which could affect the results (but due to the vastness of the subject, may be identified and not researched to save time) - i.e. using theoretic distance between two parts of a graph to limit matchings and calculating the ideal number of matchings given the connectivity of a graph.


For now, I continue to progress with the matching - which will hopefully be finished before the end of the week (another week... *sigh*). I shall update if and when any significant progress made, or next week otherwise.

Multi-matching: A mixed blessing

So... Multi-matching... slowly becoming my biggest pain (first being my seperation from my cat and second being my seperation from online gaming with Diablo III being released next week).

The matching is turning into a very tempermental system. Last time I posted, I had managed to get the "dumb matching" working with some small issues implementing it with the FDP algorithms. This has since been fixed (though it's still not implemented with the Barnes Hut due to the god awful complexity of the data structures involved). I am now given good output with similar graph drawings generated for matchings of 2 and "rougher" drawings for further matchings (to be expected, an analysis of which will be included at a later date).

Unfortunately, there is a significant runtime difference between this and the previous hard coded implementation (single matching): a difference in the region of 9x the runtime. Outputting runtimes for individual components (calculations of individual forces), the significant difference in runtime comes from the use of the tree in the global force calculations, which has more levels than the previous work (most likely due to changes when adapting it to use the multi-matching scheme).

Diagnosis and fixes are in the works as I type and further information will be posted later, but for now, know that the latest implementation of the coarsening tree is drastically slower than the previous. I will hopefully update later this week (or early next) when the issue is resolved.

Keeping reviewers, and myself, happy

This week I have been continuing with my implementation of the matching; attempting to fix the many problems it seems to have with my already existing "testing suite". Although many have been resolved or patched, there remains a larger issue when attempting to extend coordinates calculated in coarser graphs to the finer graphs (the dreaded NaN has returned).

Experience suggests this is a bug somewhere within my code where I am dividing by zero - normally due to calculating repulsive forces between a vertex and itself (resulting with a distance of zero). However, this only appears once so a more thorough examination of verbose output is required. I will update again if and when this is resolved.

Additionally, I have been working to alter my iV2012 contribution, requiring some investigation into why my MGF(CA) algorithm is faster that the OT for smaller graphs, but slows for larger graphs. Originally I hypothesised that this was due to the dimensions of the tree but failed to give any real description or evidence. Having looking into this a bit deeper, I have found my hypothesis is correct (quite significantly - in fact, its surprising my algorithm keeps up with the OT, see the below table for a comparison). Further discussion of this will be included in my technical report, and due to the amount of information, it can only be summarised in my iV2012 contribution.
 

			Levels
Graph	|V|	|E|	QT	MGF
3elt	4720	13722	14	14
uk	4824	6837	15	22
4elt	15606	45878	13	17
fe_sphere	16386	49152	14	15
finan512	74752	261120	14	36
wave	156317	1059331	15	89
dime20	224843	336024	15	52

Other changes, as requested, are being made to the submission but the limited page count is beginning to limit my additions (im convinced they set it just to play with me...).

For now, its back to "work". I shall update again when I have made an acceptable amount of progress, or when I get distracted from what I should be doing. Whichever comes first.