Martin Albrecht wrote: > 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
