[Pyrex] Fast matrices over GF(p)

[Simon King]

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). 
- Computation of nullspace is good (for a dense 1000x500 matrix over 
  GF(7), MTX was 6 times faster than Sage).

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 
  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.

So far my experience
	Cheers
	Simon