Hi there, 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: [email protected] -- To post to this group, send an email to [email protected] To unsubscribe from this group, send an email to [email protected] For more options, visit this group at http://groups.google.com/group/sage-devel URL: http://www.sagemath.org
