MatrixObj: define and implement semantics for comparing MatrixObj and VectorObj

[fingolfin]

One of the problems with treating matrices and vectors like lists is that we have to adopt the rules for comparing lists; and two lists are equal if they have equal elements. This means that all 0-dimensional vectors and matrices over all base domains should be equal, at least as long as they are lists.

To resolve that, we want to have MatrixObj and VectorObj implementations which are not lists (see also #2148). But then we should still define precise semantics as to when two vectors or two matrices compare as equal. Here is a first suggestion for how that might work:

• a vectorobj and a matrixobj are never equal
• two vectorbj are equal if they ...
  • have equal length,
  • have "compatible" base domains,
  • contain equal elements
• two matrixobj are equal if they ...
  • have equal numbers of rows,
  • have equal number of columns,
  • have "compatible" base domains,
  • contain equal elements

This leaves the question what constitutes "compatible" base domains. A simple but overly restrict definition would be to require the base domains to be equal.

This solves some problems, but would be a radical departure from how vectors in GAP
currently work, and I think that alone makes it a bad choice. There is also the matter of inconvenience caused by this when writing code.

Another definition would be to say two base domains are "compatible" if one is "contained" in the other, with compatible structure (i.e. addition/multiplication/subtraction of the "larger" base domain restrict to those of the "smaller" one.

So for fields, that just means they are compatible if one is a subfield of the other, which matches what we do right now, I think. [ UPDATE: what I really meant is that there should be a common super field containing both; for GF(q), that can be essentially tested by checkin for equal characteristic. ]

The one thing I am a bit worried here is whether we can tests this efficiently, i.e., I don't want risk introducing a bottleneck here.

Therefore, we might want to use a slightly different definition:

• a vectorobj and a matrixobj are never equal
• two vectorbj are equal if they ...
  • have equal length,
  • contain equal elements,
  • and, if they are empty, then they must have "compatible" base domains.
• two matrixobj are equal if they ...
  • have equal numbers of rows,
  • have equal number of columns,
  • have "compatible" base domains,
  • contain equal elements
  • and, if they are empty, then they must have "compatible" base domains.

This way, we only need to compare the base domains for empty vectors and matrices, which should be relatively rare. Drawback: it is a little bit less flexible. E.g. with the former model, people could write special "strict" base domains, which are not compatible with any other base domain, to get some kind of "strict typing" through the backdoor. Not sure if that's a good idea to start with, but I wanted to mention it for completeness.

As to how to implement testing for compatibility of base domains, I'd try to use method dispatch for that, to make it extensible:

DeclareOperation("IsCompatibleBaseDomain", [IsObject, IsObject]);

# identical base domains are always compatible
InstallMethod(IsCompatibleBaseDomain, IsIdenticalObj, [IsObject, IsObject], SUM_FLAGS,
function(bd1, bd2)
    if IsIdenticalObj(bd1, bd2) then return true; fi;
    TryNextMethod();
end);

# fallback: if no method fired, then assume the base domains are not compatible
InstallMethod(IsCompatibleBaseDomain,
    [IsObject, IsObject],
    ReturnFalse);

# cyclotomics are always compatible
InstallMethod(IsCompatibleBaseDomain, IsIdenticalObj,
    [IsCyclotomicCollection, IsCyclotomicCollection],
    ReturnTrue);

# FFE domains are compatible if they have equal characteristic
InstallMethod(IsCompatibleBaseDomain, IsIdenticalObj,
    [IsFFECollection, IsFFECollection],
    {bd1, bd2} -> Characteristic(bd1) = Characteristic(bd2));

[fingolfin]

I only talked about equality above, but of course this also extends to the less operator < and from there automatically to other comparisons.

[stevelinton]

I would strongly recommend limiting these operations to matrix and vector objs over the equal (even identical) base domains. This is especially true of <. Consider two vectors in some compressed format over GF(9). If you require equality with matching vectors over GF(3) then you have to ensure that the comparison order for GF(9) is consistent with the one for GF(3). Otherwise you could have a = b, c = d, a < c and d < b which would be bad, so you can't use the most efficient comparison of GF(9)-vectors (strcmp, probably) even if you never actually make a GF(3) vector.

In fact I realise this really means I want my comparisons to be representation-specific, which is, I guess, not really an option. I'd like to be able to have the same vectors over the same base domain, but in different compressed representations compare differently (and hash differently and so on). The performance costs of anything else are quite severe. On the other hand, I realise this may not be feasible -- I guess the only nice way in GAP would be to have each type of compressed vector be a different family!

[fingolfin]

@stevelinton In an ideal world, when starting from scratch, I'd agree with you, I think, including that different representations should compared differently -- for the same reasons you list. Going perhaps one little step further, I'd also prefer if comparing vectors in different reps gave an error (or at least fail), and not just false, to signal to the user that "your question is not well-formed" (otherwise these would very easily slip through by accident).

But we have more things to consider now, including how to migrate existing code incrementally to the new system. I think this is already now a big challenge, and I am afraid that if we change semantics so drastically, it becomes even more difficult, if not outright impossible. But perhaps I am just too negative -- so, we could try it: I.e. I'd write code using IsCompatibleBaseDomain, but then it's trivially, as an experiment, to turn IsCompatibleBaseDomain into a synonym for IsIdenticalObj. We can then see how much breaks, and how badly, and whether we see a chance of dealing with it.

There is another concern: Namely that of usability: from the perspective of somebody who wants to write highly efficient code, being strict about requiring identical basedomains (and even identical representations) makes a lot of sense. OTOH, when using GAP interactively, I am afraid it'll turn very quickly into a super annoying mess -- at the very least, we'd have to make sure to give the user easy to use tools which they can use to, say, add a GF(3) and a GF(9) vector after all, and also make sure to give very helpful error messages that indicate how to to do this.

In first approximation, that would probably mean providing functions to "cast" or "convert" quickly between different reps and basedomains. And they should be relatively short and easy to remember.

Last but not least, even for non-interactive code, I think it is not that outlandish that one might want to add (hypothetical) sparse GF(3) vector to a compressed GF(3) vector.... but perhaps it is... when talking and thinking about these issues, I always get the feeling that we need prototypes and write some actual code, to really understand what is needed, otherwise we'll end up solving the wrong problems.

For example, right now users can mix compressed and "plain" matrices at will, e.g. when creating a matrix group. I suppose we could change that into an error, and just demand that all matrices must be in the same rep and over the same base domain. Which certainly will break existing code, but even ignoring that, I wonder how annoying it would be for users in practice, and how many would give up due to this eventually? (Again, I suspect very well written error messages could help massively with that).

[stevelinton]

@fingolfin there's a lot to discuss here, but my main concern is specifically about < and maybe hash functions. The problem is that if you want to compare vectors/matrices in different representations, that imposes constraints on the ordering of objects in a particular representation, which can be quite expensive to satisfy. Similar issues apply to hash functions, if you want two equal objects in different representations to have the same hash value, you end up having to use a less efficient hash function for each representation.

This then has, sometimes quite severe, performance issues when you are working with collections of objects all in exactly the same representation.

[fingolfin]

@stevelinton Yes, I am (pain)fully aware of the issues with < and hashing