Teach GAP how to handle "projective matrices"

[ssiccha]

I think there is a lot of special code dealing with the fact that we can't create a GAP object which is a projective matrix and the always have to remember whether a matrix is to be understood as a usual or as a projective one.

If we were able to create "projective matrices", then a lot of code would get simpler.

[fingolfin]

This is related to issue #97 (I hadn't seen this issue here when I wrote #97, sorry).

Unfortunately, the overhead of such a wrapper likely is dramatic.

We are working a lot with these matrices. If every single interaction with a matrix suddenly has extra overhead, that sums up quickly. If done naively, with GAP objects and Objectify, I am pretty sure it would be prohibitively slow. But of course I can't be sure, so somebody could test this with a simple prototype (which could be done outside of recog; i.e. just write an object which wraps a matrix (say, a GF2 compressed 10x10 matrix) plus a single boolean flag. The benchmark the time it takes to, say, square such a matrix N times, for suitably large Ns. Then perform several similar tests, e.g. for long it takes to invert the matrix, or to extract element mat[1,1], and so on.

But it's also not quite that trivial to write such a wrapper; and to make sure it can be used everywhere in recog, not to mention GAP overall.

We might have a chance to do it, though, if we are willing to write some C code: If we added a T_PROJECTIVE kernel type (in a kernel extension), then that code could install custom IsOne and \= handlers with relatively little overhead. It would still be slower, but there is at least a chance that it could be competitive.

Note that for such things, a language like Julia (used for the OSCAR project) really shines; with that, it'd be trivial to write a "projective matrix" type which has almost zero overhead if used right. But for now that's not helpful, as we need to work within GAP alone.

[ssiccha]

Ah, I always forgot about the possible overhead of calling Objectify lots of times. Ok, that makes sense.

[fingolfin]

It would still be interesting to test this. If the overhead could somehow be kept minimal (verified by experiments and benchmarking), then using "true" projective matrices would be much, much simpler conceptually. So it is worth investigating, but just not the top priority right now. But if anybody is interested in trying, you are welcome, and I am happy to act as consultant :-)

[fingolfin]

The more I think about it, the more I think this would be sooooo nice to have.

And with the move to MatrixObj, it shouldn't even be that costly -- if matrices are stored as "proper" objects, then surely storing an extra bit to control whether they are projective or not won't cost extra... So only the suitable methods for IsOne, Order and \= are left to do, and again those should be no problem. Well, and one would need "constructors" to convert from regular to projective matrices and back.

Really, if somebody wants to experiment with this, I am very curious about it.

[fingolfin]

A quick way to get some tests in this direction going would be to take inspiration from the "matrix with memory" code in the GAP library, in lib/memory.gd and lib/memory.gi. Basically, one could duplicate that code (or at least the portions relevant to matrices), to create a IsProjectiveMatrixObj type, which delegates most computations to the wrapped element, except those for IsOne, \= and Order. Well, some further tweaks to the memory.gi code may also be needed to make it more closely aligned to the "new" IsMatrixObj API (see also e.g. this PR and the discussion on it https://github.com/gap-system/gap/pull/3563). Also, comparing/adding/multiplying/... a projective and a non-projective matrix result in an error, to help weed out bugs.

This code then may be used to perform some benchmarks, to learn how badly it impacts us performance wise.

Of course, using this together with IsObjWithMemory would be kind of a waste, with two wrapping layers. One can try to come up with clever ways to avoid this "duplication", but that's a second step, IMHO. First we want to test the principle.

[fingolfin]

Perhaps this shouldn't be IsProjectiveMatrixObj, but rather IsProjectiveObj... Point is, we don't really want to treat these matrices: indeed, probably it should not be possible to access a single entry of such an object, as it of course is only defined up to a unit... Instead, higher level APIs should be used, or the calling code should explicitly access the underlying matrix.

This way, we can't accidentally use such a "projective matrix" in code which expects to deal with regular matrices only.

[fingolfin]

IMHO the most important bit is to set up some performance benchmarks. You could use my bench.g to help with that. Then we could have some microbenchmarks, which just compare things like ..

• compare time for e.g. multiplying matrices vs. projective wrapped matrices
• overhead for creating these wrapper objects, and how it compares to operations like multiplying the matrices

[fingolfin]

Also make sure to use IsNoImmediateMethodsObject

[fingolfin]

Also you can experiment with setting IGNORE_IMMEDIATE_METHODS to disable immediate methods, to see if it has an effect.