[EM] Alternative algorithms for Yee diagrams.

Leon Smith leon.p.smith at gmail.com
Mon Dec 16 20:53:43 PST 2013

On Sun, Dec 15, 2013 at 5:55 AM, Jameson Quinn <jameson.quinn at gmail.com>wrote:

> Just eyeballing the pictures, it seems that the radii are very
> conservative. If you doubled them, it would be 4 times as fast.

Yes, that makes sense.

> I realize you want to stay on solid ground mathematically, but given how
> conservative things look, I think you probably could. Can you build the
> Hessian matrix of the tightest decisive vote margin? If so, would taking
> things to second order allow a less-conservative first-order approximation?
> (Just wild ideas, I'm not sure what I'm saying even makes sense.)

I don't know what that means,  but I'm pretty rusty on my maths.    However
I do agree that there probably is some reasonably efficient way to loosen
the (very conservative) radius bound,  as it's not taking into account the
information about which way voters are shifting,  and whether or not its
relevant to the front runner.    But it's probably not worth expending a
great deal of computational power eking out every last bit of radius,  if a
good conservative approximation is much faster.

I should mention that this solution really was all Claude,  I posed a
problem,  we discussed it,  and he ran with it and 5-ish hours later had
this,  and then he explained what he'd done.  (Nerd sniping for the win?
Although his technique did inspire another alternative algorithm I'd like
to play with myself... one that more easily generalizes from plurality
voting to any ranked voting method.)

Really it doesn't seem to be that much faster than what already exists,
 but there should be plenty of room for improvement (on both the naive and
this more sophisticated approach.)    However this does seem create much
higher-resolution images (while still being accurate) with a similar amount
of computing resources.


> 2013/12/11 Leon Smith <leon.p.smith at gmail.com>
>> Here's the result of a conversation I had with Claude Heiland-Allen
>> today about faster algorithms for generating Yee Diagrams.
>> http://mathr.co.uk/blog/2013-12-11_distance_estimation_for_voting_simulation_visualisation.html
>> I haven't run any timing tests yet,  so it's not clear if this is faster
>> as-is or not.   And there is probably substantial room for further
>> improvement... e.g. in selecting starting points more intelligently.
>> Also, the obvious generalization of this algorithm to ranked methods
>> would also slow it down a bit.  But I thought it might be of interest to
>> some people here on this list.
>> Best,
>> Leon
>> ----
>> Election-Methods mailing list - see http://electorama.com/em for list
>> info
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.electorama.com/pipermail/election-methods-electorama.com/attachments/20131216/c0f43714/attachment-0003.htm>

More information about the Election-Methods mailing list