LinearAlgebraForCAP and CategoryOfRows/Columns do not fulfil specifications

[zickgraf]

Consider the following code:

LoadPackage("LinearAlgebra");
LoadPackage("RingsForHomalg");
QQ := HomalgFieldOfRationalsInMAGMA();
M := HomalgMatrix( "[0,0,0,0]", 2, 2, QQ );
N := HomalgMatrix( "[0,0,0,0]", 2, 2, QQ );
IsZero(N);
phi := AsVectorSpaceMorphism( M );
emb_phi := KernelEmbedding( phi );
psi := AsVectorSpaceMorphism( N );
emb_psi := KernelEmbedding( psi );

Display( IsEqualForMorphisms( phi, psi ) );
Display( IsEqualForMorphisms( emb_phi, emb_psi ) );

outputs

true
false

The same happens for CategoryOfRows.

The reason is that in MAGMA, SyzygiesOfRows of a zero matrix returns a matrix with ones on the counter-diagonal. However, if homalg knows that a matrix is 0, it returns the identity matrix for SyzygiesOfRows.

Notes:

1. The same could happen any time for Singular, for example after a change as in https://github.com/homalg-project/homalg_project/pull/318 For example, if we would set the option returnSB in Singular (which applies std (=BasisOfColumns) to the output of the syz (=SyzygiesOfColums) command automatically), this would happen for Singular as well, since BasisOfRows( IdentityMatrix ) returns a matrix with ones on the counter-diagonal since the PR linked above was merged.
2. I think fixing this with caching would need the "really crisp" caching we talked about in the other issue.

[sebastianpos]

Wow, thanks for that brilliant example.

Yes, really crisp caches would help here. However, I personally would not like that solution very much, since Rows/Cols/MatrixCategory should be regarded as workhorse categories, and a really crisp caching does not comply with this point of view. But in order to provide a really save version of these categories, I also don't see another solution.

For me, the problem is that we need to know when two homalg matrices actually yield equal output for equal input. Your example demonstrates that SyzygiesOfRows does not yield equal output with respect to the operation = for two homalg matrices. A first remedy is to provide an IsEqualForMorphisms operation in Rows/Cols/MatrixCategory that also checks HasIsZero of the homalg matrices (the IsCongruentForMorphisms operation would still only check = for two homalg matrices) . Of course, as long as we don't know all possible ramifications of homalg matrices, such a solution always comes with a risk (but is at least safer than what we had unitl now).

[zickgraf]

A first remedy is to provide an IsEqualForMorphisms operation in Rows/Cols/MatrixCategory that also checks HasIsZero of the homalg matrices

So IsEqualForMorphisms( phi, psi ) should return false because HasIsZero( M ) <> HasIsZero( N )? Then I could simply ask IsZero( M ) after computing KernelEmbedding( phi ) and would get the same problem, I think.

I can think of three solutions (except really crisp caching):

1. Compare morphisms using IsIdenticalObj. I think in this case we would not need crisp caching since MatricesForHomalg stores all results anyway.
2. Test for any property a matrix could have (IsZero, IsOne, IsUpperTringularMatrix etc.) in the constructor, that is, before any computation. (Or at least test those properties that could be triggered by CAP/homalg without user interaction). That would kill most of the laziness in MatricesForHomalg I assume.
3. Use a version of MatricesForHomalg which does not have any logic.

In the last two cases, laziness and logic could partially be restored using LazyCategories and CompilerForCAP in the future. Note that the logic in LazyCategories does not suffer from the problems above since it compares objects/morphisms generically (that is, we would use IsIdenticalToZeroMorphism instead of IsZero thus would only trigger the logic for morphisms which are actually created as ZeroMorphism( ... )).

However, I can see drawbacks for any of the solutions :-(

[sebastianpos]

So IsEqualForMorphisms( phi, psi ) should return false because HasIsZero( M ) <> HasIsZero( N )? Then I could simply ask IsZero( M ) after computing KernelEmbedding( phi ) and would get the same problem, I think.

Right, unfortunately that doesn't help.

Concerning your solutions: 2) is too costly for a workhorse category 3) such a version of MatricesForHomalg does not exist to my knowledge

Concerning 1)

1. I think in this case we would not need crisp caching since `MatricesForHomalg` stores all results anyway.

Is that really true for all operations (like multiplication and addition etc.)?

[zickgraf]

3. such a version of MatricesForHomalg does not exist to my knowledge

As far as I know it exists in theory, simply by loading LIMATEmp.gi instead of LIMAT.gi in MatricesForHomalg (LIMATEmp.gi should contain exactly the logic in LIMAT.gi which is needed for empty matrices, and nothing more). However, there is no official switch (and if it were, it would not be ring specific but global), and it is untested.

Is that really true for all operations (like multiplication and addition etc.)?

Ah, I thought that these would not be a problem because the result is deterministic anyway, but now I realize that it would still break the specification.

Then I'm out of ideas :-(

[sebastianpos]

For a start, we could try to provide a method for homalg matrices that delegates syzygy computations directly to the oracle no matter what knowledge it possesses, use that method in the implementation of Rows/Cols/MatrixCategory, and measure the effect.

[zickgraf]

and measure the effect

Do you have concrete tests in mind? If yes, I/we could simply comment out the optimization(s) in MatricesForHomalg/gap/LIMAT.gi and run the tests. I just did this for the Freyd tests and can see no meaningful difference (I know that commenting out worked because I get some warnings an empty matrix is about to get evaluated! but I have checked that the tests failing due to that do not contribute to the runtime of the tests in a significant way).

[sebastianpos]

The Freyd tests are the important tests for me. To my knowledge, the tests in https://github.com/homalg-project/ZariskiFrames/ heavily depend on the category of rows.

[mohamed-barakat]

To my knowledge, the tests in https://github.com/homalg-project/ZariskiFrames/ heavily depend on the category of rows.

I can confirm this statement.

[zickgraf]

I have tested ZariskiFrames using this branch which disables the logic for syzygies and, again, I can see no meaningful difference in the runtimes.

If these tests are representative for current applications, providing and using a method for homalg matrices that delegates syzygy computations directly to the oracle should not cause regressions.

However, the same would need to be done for all other homalg operations used by CategoryOfRows, for example RightDivide, and I assume sooner or later one has an example where one would like to have the logic. For me, the central question is: Why do such optimizations cause problems for CAP but not for homalg? If you think this is a worthwhile question to ask, maybe we can keep this issue as is and discuss the question verbally eventually.

[sebastianpos]

Why do such optimizations cause problems for CAP but not for homalg?

Yes, keep this issue open.

I would not judge it to be urgent, and the reason for that is that I gained my confidence exactly by the fact that homalg hasn't run into problems with its matrix logic (yet).

Note that the specifications in CAP were in particular introduced in order to have a way to reason about what we are doing, so of course, I would like to see this issue resolved sooner or later.

[mohamed-barakat]

Here is another example:

gap> Z6 := HomalgRingOfIntegers( 6 );
Z/( 6 )
gap> m := HomalgMatrix( [ 6 ], 1, 1, Z6 );
<A 1 x 1 matrix over a residue class ring>
gap> n := DecideZero( m );
<A 1 x 1 zero matrix over a residue class ring>
gap> Display( m );
[ [  6 ] ]

modulo [ 6 ]
gap> Display( n );
[ [  0 ] ]

modulo [ 6 ]
gap> SyzygiesOfRows( m );
<A non-zero 1 x 1 matrix over a residue class ring>
gap> SyzygiesOfRows( n );
<An unevaluated 1 x 1 identity matrix over a residue class ring>
gap> m;
<A 1 x 1 matrix over a residue class ring>
gap> m = n;
true
gap> m;
<A 1 x 1 zero matrix over a residue class ring>
gap> SyzygiesOfRows( m ) = SyzygiesOfRows( n );
false