State of Play and plans

[stevelinton]

What's committed at the moment seems (after a few unstructured tests) to work. You can create, access, set entries in, do arithmetic operations on, and echelize slab-sized matrices.

Design choices:

• These objects are not integrated with existing finite field, list or matrix categories at all. There are some convenience functions installed using InstallOtherMethod, but they do NOT obey the usual list semantics or ordering of FFEs.
• Elements and matrices over each distinct field are in a distinct family. There is no attempt to identify elements of subfields K of one field L with elements of the finite field isomorphic to K.
• DSpaces are never stored and are not exposed at GAP level

To dos or concerns:

• [x] Caching of fields and families using MemoizePosIntFunction means that using larger field sizes wastes a lot of memory in the cache or fails. Need a more sophisticated cache
• [x] Function naming is not consistent and is possibly rather clumsy. Some more things could maybe be usefully gathered up into Operations and sets of Methods
• [x] Commenting and documentation is still very incomplete
• [x] Argument checking is largely missing.
• [ ] The connection between a matrix or FELT and it's field goes via a call out to GAP and inspection of the family. This avoids storing Obj values in T_DATOBJ objects (which has implications for save/load and garbage collection, but seems cumbersome. Could use Type data to shorter the chain a bit.
• [x] The only nicer-level function that uses Echelize is Inverse -- we could install (other) methods for RankMat, NullSpaceMat, etc. I'm not sure if the determinant value is reliable yet.
• [x] Would be nice, and probably trivial to be able to convert BitString objects to and from Blists.
• [x] More efficient conversions between VECFFE, VecGF2 and Vec8Bit objects and rows of meataxe64 matrices -- I'm working on that
• [x] The next big step is to extend and document GAP bindings for the functions layer of MTX64. This first needs IO routines at the Dfmt level, which are in io.h, but not documented.
• [x] Building the assembler somehow and deciding which one to load at runtime all needs to be tackled.
• [x] The OS X assembler problem -- my current thinking is a short programme, probably in GAP that pre-processes assembler files, and then needs adding to the build setup.
• [x] More Tests
• [ ] Can these be MatrixObj objects? If not, do the MatrixObj specifications need review.
• [x] hash functions

[stevelinton]

I've added a script etc/asmfix.g which converts assembler for OSX. It appears to work I haven't tried to work out how to get automake to run it, or how to elegantly select which set of assembler to use.

[stevelinton]

Following discussion with Richard, the "choosing which assembler to use at runtime" problem will likely go away. A future version of mtx64 will include all versions and use the CPUID instruction to decide which one to use.

[markuspf]

I tried implementing conversion between bitstrings and blists. Its a bit fiddly to make sure that BIPEB is lined up with uint64_t. Functions for bitstrings seem to be incomplete as well (no function to create a bitstring, number of bits not set (I assume that in a meataxe64 bitstring uint64_t *bs, bs[0] is the number of bits, and bs[1] is the number of bits that are set? in my branch I tried to add some documentation while I go along to make it easier for others to fiddle around if they feel the need.

[markuspf]

I also think we should at some point split up meataxe64.c into parts (one for bitsttrings, one for finite fields, one for matrices at least).

[stevelinton]

@markuspf I think we need to assume that BIPEB is 64. There is no way meataxe64 is ever going to work with any other wordlength. I'd suggest that the package AvailabilityTest just fail if GAPInfo.BytesPerVariable isn't 8. I agree about splitting up meataxe64.c, though. It's getting quite long.

[stevelinton]

I just added row-at-a-time access for GF2 so you can extract a row of a MTX64 matrix as a GF2 compressed vector. After some checking, it's just a memcpy. 8bit is going to be a bit more interesting, although I think I can feel a lookup table coming on...

[stevelinton]

8bit is now in place. That should be all the kernel programming for the conversions, which run very fast. With a few GAP level routines to handle whole matrices, we should be good.

[stevelinton]

I've now got enough conversions etc. to make it convenient to do some benchmarks, which I'm doing now. As one data point, over GF(2) to do a single matrix multiply (squaring a random matrix) it becomes quicker to convert to MTX64, multiply and convert back, rather than use the builtin compressed matrix multiply, at about 500 dimensions. Just the multiply without the conversions crosses over at about 50 dimensions. For GF(3) it's even more dramatic, with crossover at about 100 dimensions and about 100-fold performance difference for 10000 dimensions.

[stevelinton]

A couple of updates:

• matrix read and write is there, so it should be possible to bridge slab and function levels.
• Richard is reworking the assembler layer, so it should eventually detect the hardware automatically and choose an appropriate implementation

[stevelinton]

Just FYI. There is now an implementation of a recursive echelize in echelzie.gi which is much more efficient than just using the slab echelize for matrices over a few hundred dimensions. At "slab size" 50K or so, it is not much slower than a multiply, and actually faster if all you want is the rank, for instance. I'm reworking it following experience of writing it the first time and discussion with Richard, but, for instance echelizing a 40Kx40K matrix over GF(157) takes less than 20 minutes on my laptop.