(I'm taking this thread *off* the Cython lists and onto sage-devel
where it belongs.)
On Mon, Mar 24, 2008 at 1:38 PM, Simon King <[EMAIL PROTECTED]> wrote:
> Dear Robert,
>
>
> On Mon, 24 Mar 2008, Robert Bradshaw wrote:
> >
> > Some of us ran into MeatAxe before, but no one had any experience with it
> or
> > knew anyone who used it, so nothing ever happened of it. I was thinking
> since
> > you actually use it (and have a Cython wrapper) you would know what it's
> > strengths/weaknesses are and whether or not it would be worth including in
> > Sage.
>
> Ok, then i think i will write to Sage devel in a few days and post some
> code, so that people can test it.
>
> A few words on strengths/weaknesses:
>
> Main Strength of MeatAxe:
> IMO, it is a slim and simple data structure. Hence, many basic operations
> such as copying and (un)pickling are a lot faster with MTX than with Sage
> matrices. Also, the hash and test for equality of my wrapper works quite
> fast: Although i do not (yet) cache the hash, using a 500x500 MTX matrix
> as key for looking up in a dictionary is (on average) 0.57 ms, while it is
> (on average) 819 ms with the corresponding Sage matrix, even though its
> hash is already cached (if the hash isn't known, one look-up takes more
> than 2s)!
>
> 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.
> - 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.
> Weak points in arithmetics:
> - Multiplication of two matrices (slower than Sage by a factor 2.5 for
> 500x500 matrices over GF(7));
> - exponentiation of a matrix.
>
> Conceptual weakness:
> - Restriction to fields of order <256
> - MeatAxe (at least version 2.2.3 of 1997 that i am using) relies on
^^^^^^^^^^^^^^^^^^^^^^^^^^
That's a big (!!!) warning to me, unless you want to become the
official maintainer and make new releases...
> 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.
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?
-- William
--~--~---------~--~----~------------~-------~--~----~
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
-~----------~----~----~----~------~----~------~--~---
