[Pyrex] Fast matrices over GF(p)

[Robert Bradshaw]

On Mar 21, 2008, at 3:40 PM, Simon King wrote:

> Dear Simon, dear Robert,
>
>> Use these functions instead:
>>
>> cdef extern from "Python.h":
>>
>>     object PyString_FromStringAndSize(char *s, Py_ssize_t len)
>>     char* PyString_AsString(object string)
>
> Again, thank you for your valuable help!
>
> As part of a project on the computation of cohomology rings (in  
> terms of
> minimal generators of a graded commutative algebra and a minimal  
> set of
> algebraic relations between them) for finite p-groups, i wrote a
> Pyrex/Cython class "MTX" wrapping Ringe's MeatAxe matrices.
>
> Disadvantage of MTX:
>  It is only for small fields (order <256). But i don't need more.
>
> Advantage:
>  In some tests (dense matrices over GF(7), size 200x200), addition of
> matrices, multiplication by scalars, inversion and various basic
> operations (e.g. transposition) turned out to be faster with MTX  
> than with
> the matrices used by Sage (addition and inversion only slightly,  
> but the
> rest by factors of more than 100).
>
> And, with your help, pickling/unpickling is faster as well, namely  
> by a
> factor of >200 compared with Sage-matrices.
>
> Do you know another piece of free software that is good in dealing  
> with
> matrices over small fields? Perhaps there is some further improvement
> possible, specifically if the matrices are of large size (i need  
> kernels
> of matrices with >1000 rows and columns)? Any hint is welcome!

Sounds very interesting! Sage has been mostly optimized to deal with  
very large matrices, and GF(p) for p barely fitting into a word (to  
facilitate linear algebra over Z and Q). It sounds like your code  
does much better for small p. Do you mind if I forward your email  
onto sage-devel?

- Robert