On Monday 28 November 2011, Simon King wrote: > Hi Martin, Hi Simon,
> Indeed. The prime slice (earlier, you named it bitslice) approach > should not be forgotten. Yep, btislice (p=2) and prime slice (p > 2) :) > But I wonder one thing: How would you compute echelon forms using > bitslice? Is that as straight forward as for matrix multiplication? You'd reduce it to matrix-matrix multiplication essentially. For this one needs Triangular System Solving with Matrices (which also reduces to matrix- matrix products + a base case) and a decent base case implementation (a la MeatAxe or using ideas like Newton-John (formerly Travolta) tables). Here's an implementation for GF(2^e): https://bitbucket.org/malb/m4rie/src/171b1528e4a3/src/ple.c note that this implementation is much faster than the Newton-John table based approach (which I'd expect to be faster than MeatAxe when extended to general p, but I am not sure). E.g.,: sage: A = random_matrix(GF(2^7,'a'),6000,6000) sage: %time copy(A).echelonize('travolta') CPU times: user 13.00 s, sys: 0.03 s, total: 13.03 s Wall time: 13.09 s sage: %time copy(A).echelonize('ple') CPU times: user 4.95 s, sys: 0.04 s, total: 4.98 s Wall time: 5.01 s Note that this also means that your benchmark examples on the M4RIE got quite a bit faster using M4RIE compared to when we benchmarked them, i.e., you should see some additional speed up using the development code of M4RIE (I need to cut a new SPKG). > > On the other hand, talking about the "long term" isn't what Sage is > > usually about, ... > > I guess you speak here about implementation, not about features, > right? So, you wouldn't mind to have a particular matrix > implementation for some time and wouldn't mind to change as soon as > you find something better? Yes, that's of course possible. I'd rather work on a prime-slice implementation, but if you prefer to have libCMeatAxe now, I'd of course not oppose it. > > Oh, LinBox does support > > non-prime finite fields but even Clément couldn't make it work easily > > IIRC. > > I remember they have non-prime fields. But at least #4260 doesn't use > it. Yep, that's correct. > Best regards, > Simon 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
