M4RIE: linear algebra over small extensions of GF(2)
Martin Albrecht
my coding spring project here at Sage Days 24 was/is to write a new
library for dense linear algebra over small extensions of GF(2).
The main idea is to represent matrices over GF(2^e) internally as M4RI
matrices over GF(2) in a row major flat representation. This allows to
re-use many of the M4RI functions such as addition of rows and matrices,
stacking, augmenting etc. For the elimination and multiplication base
cases we use a simple trick inspired by M4RI: we compute all possible
multiplications of a pivot row and store the result in a table. Then, we
use the M4RI functions to perform table look ups and row elimination
using the tables constructed this way.
I haven't implemented any asymptotically fast methods yet but I hope to
finish with Strassen multiplication this week. Asymptotically fast
elimination requires slightly more infrastructure (TRSM, taking care of
offsets etc.) If anybody is interested in helping out that would be
greatly appreciated. Also, I guess one should also try M4RI (the
algorithm) for GF(2^2).
In any case, you can see some first results at
http://wiki.sagemath.org/days24/projects/gf2e
Here are some preliminary benchmarks for row echelon forms of dense
random n x n matrices over GF(2^4)
|| n || Sage 4.5 || NTL/2 || Magma || M4RIE (old)|| M4RIE (new) ||
|| 1000 || 49.49 || 18.84 || 0.090 || 0.097 || 0.046 ||
|| 2000 || 429.05 || 149.11|| 0.510 || 0.529 || 0.28 ||
|| 3000 || 1494.33 ||526.57 || 1.640 || 2.315 || 1.00 ||
Bottom line it is much much faster than what we have in Sage right now
(which is the generic implementation). Also note that switching to NTL
would not improve things much.
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.
I've prepared a new libm4ri SPKG which contains both an updated M4RI
(which exports more internals such that we can use it from M4RIE) and
libm4rie.
http://trac.sagemath.org/sage_trac/ticket/9562
I built my new code on
* t2: Solaris (cannot run tests because of missing libstdc++?)
* eno: 64-bit Linux
* iras: 64-bit Iras
* bsd: 32-bit OS X
Mike tried to build it on Cygwin and there are issues. Also there are some
doctest failures I have yet to fix.
Anyway ... question: Do we want my new code in Sage?
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://www.informatik.uni-bremen.de/~malb
_jab: martinr...@jabber.ccc.de
Robert Miller
<martinr...@googlemail.com> wrote:
> Anyway ... question: Do we want my new code in Sage?
I assume nobody has replied because it's such an obvious yes!
>
> Cheers,
> Martin
>
--
Robert L. Miller
http://www.rlmiller.org/
Bill Hart
Bill Hart
M4RIE, LOL!! What an awesome name.
I don't have time to work on this for a couple of weeks, but if you
are still going after that, I might check out the code and see if
there is anything I can contribute. It sounds like you are making very
good progress so far, so maybe you'll be all done by then.
Looks like great work/fun anyway.
Bill.
Martin Albrecht
I will finish whatever I can this week. Afterwards I won't probably
actively develop the code for a few weeks. I just implemented
Strassen-Winograd multiplication which should (after some tuning) give
some indication how much can be gained using asymptotically fast
elimination. I'd start implementing that in September or so (maybe
earlier if someone wants to work on this with me).
Tom Boothby
> 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?
> Anyway ... question: Do we want my new code in Sage?
+1
Carl Witty
<martinr...@googlemail.com> wrote:
...
Pretty pictures! It would be nice, though, to have some sort of
indication on the picture whether Magma is red or blue...
For example, you could put "Magma" next to the 4 on the right-hand
scale, and "Sage" next to the -4 -- or vice-versa, whichever is
appropriate :)
Carl
Martin Albrecht
> --
> To post to this group, send an email to sage-...@googlegroups.com
> To unsubscribe from this group, send an email to sage-devel+...@googlegroups.com
> For more options, visit this group at http://groups.google.com/group/sage-devel
> URL: http://www.sagemath.org
Martin Albrecht
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: martinr...@jabber.ccc.de