Hi Simon, On 27 November 2011 20:42, Simon King <simon.k...@uni-jena.de> wrote: > Hi! > > Since quite some time, I'm using the Aachen C-MeatAxe as backend for > linear algebra over fields of size < 255. I think I am now able to > produce spkg+patch, as an optional and hopefully eventually standard > package. > > I see the additional matrix backend as a complement of M4RI (which is > over GF(2)), M4RIE (which is over GF(2^e), 1<e<11, see trac ticket > #9562) and Linbox (GF(p), p prime, see trac ticket #4260). > > But before being able to finish the spkg, I need some advice: Am I > patching MeatAxe, or am I creating a fork? I think the answer has an > impact on some details of the spkg I am now creating.
I think you are effectively forking MeatAxe and in fact I think you should set up an independent website etc. for your project. It's pretty far from standard MeatAxe and much improved compared to it IMHO. Of course, you should try before to submit your patches to MeatAxe. > My starting point is C-MeatAxe version 2.2.4. This version is not the > most recent, but it is the *only* version that is licenced under GPL > 2+. In fact, apart from the licence, it is identic with 2.2.3. I > tested that the linear algebra in it is as fast as in the more recent > versions. > > But actually I am not just wrapping it. First of all, MeatAxe is a > collection of executables -- and I strip it down to a C-library. I fix > some bugs and get rid of compiler warnings. And most importantly, I > implement Winograd-Strassen multiplication (MeatAxe is only using > school book multiplication). > > In the developer manual, I read that an spkg is supposed to provide > the *original* sources that are not under version control, and if > changes are made then the changes should be made by applying patches > -- unless the spkg *is* upstream. > > In my case, the patch would be about 600kB, and it adds fairly non- > trivial stuff. So, should my spkg be called > "meataxe-2.2.4.p0.spkg" (patching the original sources), or > "libmeataxe-1.0.spkg" (considering the modified sources as upstream)? > Is the latter allowed by GPL2+? Yes, it is allowed. > Last, but by no means least, I'm showing you some benchmarks. The > timings are with spkg+patch, the corresponding times for unpatched > sage are given in the comments. > > sage: MS = MatrixSpace(GF(5^3,'y'),1500,2000) > sage: %time A = MS.random_element() > CPU times: user 0.22 s, sys: 0.00 s, total: 0.22 s > Wall time: 0.22 s # unpatched: 4.75 s > sage: %time A.echelon_form() > CPU times: user 6.67 s, sys: 0.00 s, total: 6.68 s > Wall time: 6.70 s # unpatched: 282.15 s > 1500 x 2000 dense matrix over Finite Field in y of size 5^3 > sage: MS = MatrixSpace(GF(5^3,'y'),2000) > sage: A = MS.random_element() > sage: %time ~A > CPU times: user 23.46 s, sys: 0.04 s, total: 23.50 s > Wall time: 23.57 s # unpatched: 1090.13 s > 2000 x 2000 dense matrix over Finite Field in y of size 5^3 > sage: B = MS.random_element() > sage: %time A*B > CPU times: user 7.44 s, sys: 0.01 s, total: 7.45 s > Wall time: 7.48 s # unpatched: 746.33 s > 2000 x 2000 dense matrix over Finite Field in y of size 5^3 > > I'm afraid I am not able to compare this with Magma and Mathematica. > > Do you see apparent reasons why "LibMeatAxe" could not (eventually) be > a standard package? I am definitely all for making it at least an optional package. That being said, I'm not convinced yet that going for MeatAxe is such a good strategy eventually. My impression is that going for LinBox + Karatsuba & Prime-slice representation should be faster. By "Prime-slice" I mean a representation where the coefficients for each degree of the polynomial representation are stored in matrices mod p. So for your example above I'd get sage: A = random_matrix(GF(5),2000,2000) sage: B = random_matrix(GF(5),2000,2000) sage: %time A*B CPU times: user 0.94 s, sys: 0.01 s, total: 0.95 s Wall time: 0.96 s sage: 0.95 * 6 # six multiplications needed for Karatsuba at degree 3 5.70000000000000 which isn't that much faster than your 7.5 seconds, but the approach could be easily made to work for all extensions up to, say, degree, 10 and wouldn't be limited to p < 255. On the other hand, talking about the "long term" isn't what Sage is usually about, but I figured I should at least mention that I'm not convinced by the approach of MeatAxe. Oh, LinBox does support non-prime finite fields but even Clément couldn't make it work easily IIRC. 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: 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
