On Thursday 22 July 2010, Tom Boothby wrote: > > I should point out that the strategy for multiplication in Tom and > > Robert's paper http://arxiv.org/abs/0901.1413 is likely to be better. > > Judging from the timings in that paper we are about a factor of two > > behind them. I plan to implement/port their very cool trick for finite > > extension fields at some point in the future. The trick is limited to > > multiplication as far as I understand it thus it might make still sense > > to consider my representation for the elimination base case etc. > > Our runtime is something like O(e^1.6 n^2.8) using Karatsuba on the > matrix slices. Looks like you've implemented a lookup table for your > finite field arithmetic? If that's only twice as slow as the > bitslicing strategy, I'm very impressed -- especially since you have > to use 16 bits to store a 9-bit field element due to alignment. I > guess the real question is, how quickly can one transition between the > two representations?
Hi Tom et al, I've implemented the bitslice Karatsuba trick for GF(2^2) in M4RIE now. In all cases this is much faster than the old code using the Travolta tables + Strassen. On Intel CPUs I get a speed-up of about 2-3 but on some Opterons it can be as much as 7.Also, on Intel CPUs the conversion time between formats is almost irrelevant (for the considered dimensions) but on Opterons it is noticeable (but not dominant). I've written a bit more about this at http://martinralbrecht.wordpress.com/2010/08/15/ Sorry for linking to my own blog, it made sense to write it up there since it has tables, LaTeX formulae etc. Cheers, Martin -- name: Martin Albrecht _pgp: http://pgp.mit.edu:11371/pks/lookup?op=get&search=0x8EF0DC99 _otr: 47F43D1A 5D68C36F 468BAEBA 640E8856 D7951CCF _www: http://martinralbrecht.wordpress.com/ _jab: martinralbre...@jabber.ccc.de -- To post to this group, send an email to sage-devel@googlegroups.com To unsubscribe from this group, send an email to sage-devel+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-devel URL: http://www.sagemath.org
