Hi, I still did not look at the code of Meat axe, but I remember having been really impressed a presentation at MSRI last year about MeatAxe. The timings were really impressive especially the matmul ones. So I am really surprised by your experience with slow matmul.
>>> The strength of MTX in arithmetics is IMO: >>> - difference of two matrices (>300 times faster than Sage); >>> - multiplication of a matrix with a scalar (actually this is a very weak >>> point of Sage matrices, namely it is slower than the multiplication of >>> two matrices). >>> >> I just want to point out that things like this are slow in Sage only >> because nobody has yet bothered to implement code to do it, >> so the operation just falls back to some very slow generic method. >> Any of the above could likely be made as fast or faster than MTX >> in Sage. I would much prefer speeding up Sage matrices rather >> than incorporating MTX into Sage, since the result will in the former >> case will be much easier for users to understand and lots >> of other codes benefits. If we go the later route (use MTX), we get >> a much more complicated situation -- and just put off the inevitable >> optimization of Sage's matrices. >> > > +1 on that point: either Sage Linalg or LinBox can be improved on these computations, since they are definitely not optimized for it. And multiplying a matrix by a scalar, is not such a big application to justify switching to a new software (matmul could definitely be!) > I tend to agree with all of the above - LinBox properly hooked into > Sage should beat anything out there. If it doesn't we know where we > need to improve LinBox :) > > +1. I really want to implement the small field matmul using the ideas of http://hal.archives-ouvertes.fr/hal-00259950/fr/ The idea is to take advantage of both worlds: * compressed storage * double floating arithmetic (=>BLAS, SSE, etc) The trick to store k elts in a double as a polynomial evaluated in a power of 2. Then multiplying two of such elements together (floating point mul) is a convolution of the polynomials. So if you store one of the 2 inputs in reverse order, you get a dot product of k elements for the price of 1 floating point mul. Experiments by Dumas showed computations speed around 20Gflops on a machine where ATLAS was nearly only 6Gflops. I plan to update fflas-ffpack, linbox and consequently sage with this trick soon. I think in a first attempt, only matmul should be addressed: * it would be such a pain to deal with more elaborate algorithms, performing permutations and block decomposition by views on the matrix * matmul is really the root of all efficiency, so it should already provide a good speed-up to many computations >>> - Computation of nullspace is good (for a dense 1000x500 matrix over >>> GF(7), MTX was 6 times faster than Sage). >>> >> Why? It's worth seeing if Linbox properly used can beat MTX -- I mean >> dense nullspace of matrices of that sort of size is I think exactly where >> linbox should be beating everything else, at least if one has a properly >> optimized BLAS. >> >> I am surprised that nullspace could be so efficient without a good matmul. >>> multiplication tables that are stored in a file in the current >>> directory, and whose creation relies on an executable "maketab". This, i >>> think, is nasty. I don't know if the more recent versions have the >>> multiplication tables in memory. Also i don't know if my wrapper would >>> still work if i'd change to the new MeatAxe. >>> I don't understand this focus on "files" with meataxe. >> By the way, we don't even have a "matrix over Givaro finite fields" type >> in Sage at present, which would likely be very fast for arithmetic over GF(q) >> for q < 65,000. Using Linbox it would likely be pretty easy to add such >> a type to Sage. Comments Clement? >> Do you mean extension field using givaro? I agree this has to be done For prime fields, the best way to use linbox is the Modular<double> finite field in a clear transparent way. I am currently designing linbox-2.0 matrix interface to help doing these interfaces as clear and copy-free as possible. Clément --~--~---------~--~----~------------~-------~--~----~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://www.sagemath.org -~----------~----~----~----~------~----~------~--~---
