Bugs in how ClusterQuiver handles coefficients

[Etn40ff]

The code performing mutations on ClusterQuiver does not handle properly
coefficients. In particular this introduces arrows in between frozen vertices
yielding issues when computing mutation classes.
Here is the smallest example I could come up with.

sage: B = matrix(3,[0,1,-1]); B
[ 0]
[ 1]
[-1]
sage: Q = ClusterQuiver(B)
sage: list(Q.mutation_class())
Traceback (most recent call last):
...
ValueError: The input digraph contains edges within the frozen vertices

The problem is that, rather than performing matrix mutations the code calls an
helper function performing digraph mutations. I do not see the rationale behind
this. Not only it is slower than the simple matrix operations needed to perform
mutations on matrices but it is also giving issues.

Here is another similar issue:

sage: B = matrix(3,[0,1,-1]); B
[ 0]
[ 1]
[-1]
sage: Q = ClusterQuiver(B)
sage: Q.mutate(0)
sage: Q.b_matrix()	# this gives the expected output
[ 0]
[-1]
[ 1]
sage: Q.show()		# this output is wrong!!!

Note that consistency tests (which in theory should not be needed and which
contribute to the overall slowdown) are performed in __init__ only when
creating a ClusterQuiver from a digraph.

Finally coefficients also force wrong answers from the algorithm computing
mutations classes:

sage: B = Matrix([[0,1,0],[-1,0,1],[0,-1,0],[0,1,0],[0,1,-1],[0,-1,0]])
sage: Q = ClusterQuiver(B)
sage: Q.mutation_class()
Traceback (most recent call last):
...
ValueError: The mutation class can - for infinite mutation types - only be computed up to a given depth

Depends on #24924

CC: @sagetrac-gmoose05 @stumpc5 @sagetrac-drupel @sagetrac-vpilaud @slel

Component: combinatorics

Keywords: ClusterSeed, mutations, cluster

Stopgaps: #22464

Author: Frédéric Chapoton

Branch/Commit: public/22381 @ c719703

Issue created by migration from https://trac.sagemath.org/ticket/22381

[Etn40ff]

comment:1

Actually a better example for the third issue:

sage: B = Matrix([[0,1,0],[-1,0,1],[0,-1,0],[2,0,0]])
sage: Q = ClusterQuiver(B)
sage: Q.is_mutation_finite()
False

[Etn40ff]

Branch: public/ticket/22381

[Etn40ff]

Commit: 67e6b5b

[Etn40ff]

New commits:

67e6b5b

Add stopgap for trac:22381

[Etn40ff]

Changed commit from 67e6b5b to none

[Etn40ff]

Changed branch from public/ticket/22381 to none

[Etn40ff]

Stopgaps: 22464

[slel]

Changed stopgaps from 22464 to #22464

[fchapoton]

Branch: u/chapoton/22381

[fchapoton]

New commits:

bf0e950

trac 22381 do not introduce arrows between frozen vertices

[fchapoton]

Commit: bf0e950

[sagetrac-git]

Changed commit from bf0e950 to 4cef3ac

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

4cef3ac

another py3-related change

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

d8358bb

other py3 details

[sagetrac-git]

Changed commit from 4cef3ac to d8358bb

[sagetrac-git]

Changed commit from d8358bb to 45607b1

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

45607b1

another py3 change

[fchapoton]

Author: Frédéric Chapoton

[Etn40ff]

comment:12

Thank you for dealing with this Frédéric. I wanted to help with the review but I have a quite old version of sage right now and recompiling I bumped into #24575. I'll return to this once that is fixed. If anyone gets to it before I do please do not feel obliged to wait for me.

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

ce75cfc

more py3-compatibility details

[sagetrac-git]

Changed commit from 45607b1 to ce75cfc

[Etn40ff]

comment:52

Replying to @stumpc5:

sage: A = ClusterAlgebra(['D',10], principal_coefficients=True)
sage: %time _ = list(A.seeds(mutating_F=False))

Does this use matrix mutation, or another mutation algorithm you implemented?

A bit of both: we mutate the top part by sage.matrix.matrix0.Matrix.mutate and the bottom part by hand. This is because we just wanted to keep c-vectors separate. We even perform several other computations that are needed for cluster algebras and that can be easily dropped if one only cares about quivers.

If one wanted to be smarter this could be entirely done with your cytonized code.

[stumpc5]

comment:53

If one wanted to be smarter this could be entirely done with your cytonized code.

So let me rephrase to see if I understand correctly and whether we are on the same page:

The best version of your suggestion is that we could compute the complete mutation class of a symmetrizable matrix using the cythonized mutate method in matrix0.pyx and then compute all canonical forms after.

I will try to produce something similar to this and see how it compares...

[Etn40ff]

comment:54

Yes, this is more or less what I was thinking of.

If the canonical form is able to distinguish also quivers with coefficients I would suggest this algorithm:

B input matrix possibly with coefficients

Append an identity matrix to B

perfome mutations with cytonized mutate on the resulting matrix and use the last n entries in each column to distinguish matrices.

return canonical form of the resulting matrices.

This last step is not necessary if, at some stage, we find an identity matrix among the possibly permuted coefficient rows of a matrix. I am not sure it is worth testing for this though.

[stumpc5]

Attachment: 2018_03-CythonTestMatrixMutation.py.gz

[stumpc5]

comment:55

I have provided a toy example how to do the mutations on matrices instead at https://github.com/sagemath/sage/files/ticket22381/2018_03-CythonTestMatrixMutation.py..gz

It is what I think is an improved version of what Salvatore and I discussed yesterday:

• I do not add any artificial principal coefficients but immediately do all possible matrix mutations and check for isomorphisms along the way. Reason: we have to canonicalize all matrices in the end anyways to check for duplicates. It is thus faster to do the canonicalization immediately after finding it and discarding if already existing (so we save additional mutations).

• This is now ~2 times faster that what I had before using digraph mutation, and not yet completely optimized.

• On the downside, more than 50% of the time is already spent in the canonical form cython function, so there is not much improvement possible currently.

• On the upside, this new code is much cleaner, since I never canonicalize the matrices themselves, but only save the hashes of their canonical forms.

Despite this code, I am not convinced it is worth changing all of mutation_class to use this new code given that I haven't used it in years and I would certainly takes days to get this done + proper debugging afterwards.

What do you think how to proceed here?

[stumpc5]

Attachment: 2018_03-CythonTestMatrixMutation.2.py.gz

[stumpc5]

comment:56

Okay, I changed to a different canonical labelling algorithm (namely bliss) which speeded by another factor of ~2, see https://github.com/sagemath/sage-prod/files/10658986/2018_03-CythonTestMatrixMutation.2.py.gz . Additional advantage now is that only 10% of the time is spent on the canonicalization, so there are multiple places for improvements.

[stumpc5]

comment:57

(The reason for this time improvement is that I don't care anymore about the automorphism group since matrix mutation is fast and I can afford to do all mutations at all vertices rather than knowing the automorphism group orbits.)

[stumpc5]

comment:58

Attachment: 2018_03-CythonTestMatrixMutation.3.py.gz

The newest version https://github.com/sagemath/sage-prod/files/10658987/2018_03-CythonTestMatrixMutation.3.py.gz is now in total 6 times faster than the original implementation. Now, 1/3 of the time is spent in the bliss method, and 1/2 of the time is spent preparing for bliss.

[stumpc5]

comment:59

@Salvatore, I have a question concerning

Thm: B1 and B2 in the mutation class of Bp are equivalent if and only if the sets of their c-vectors coincide.

and in particular

This last step is not necessary if, at some stage, we find an identity matrix among the possibly permuted coefficient rows of a matrix. I am not sure it is worth testing for this though.

This seems not correct, since I believe you need to consider c-vectors up to index permutations:

Consider bipartite A3 with principal coefficients and mutable vertices 0,1,2. Then vertices 0 and 2 form an orbit of its graph automorphism group and mutating at 0 and mutating at 2 yield the same quiver, while in the first case, you have c-vectors

[(1, 0, 0), (0, 1, 1), (0, 0, -1)]

and in the second case

[(-1, 0, 0), (1, 1, 0), (0, 0, 1)]

which do not coincide.

Am I correct that there is no situation where you can forget about the isomorphism test, or am I misunderstanding what you meant?

In type A3, we have 10 different unlabelled quivers, while your algorithm found 14 = Cat(4).

[stumpc5]

comment:60

Replying to @stumpc5:

@Salvatore, I have a question concerning

Thm: B1 and B2 in the mutation class of Bp are equivalent if and only if the sets of their c-vectors coincide.

and in particular

This last step is not necessary if, at some stage, we find an identity matrix among the possibly permuted coefficient rows of a matrix. I am not sure it is worth testing for this though.

This seems not correct, since I believe you need to consider c-vectors up to index permutations:

Consider bipartite A3 with principal coefficients and mutable vertices 0,1,2. Then vertices 0 and 2 form an orbit of its graph automorphism group and mutating at 0 and mutating at 2 yield the same quiver, while in the first case, you have c-vectors

[(1, 0, 0), (0, 1, 1), (0, 0, -1)]

and in the second case

[(-1, 0, 0), (1, 1, 0), (0, 0, 1)]

which do not coincide.

Am I correct that there is no situation where you can forget about the isomorphism test, or am I misunderstanding what you meant?

In type A3, we have 10 different unlabelled quivers, while your algorithm found 14 = Cat(4); how did you propose to get the 10 graph (or b-matrix) isomophism types out of this?

[Etn40ff]

comment:61

Hi Christian,
sorry for being AFK for some time: this is quite a busy period so I am not as responsive as I should.

Concerning your question I guess you are right: from the perspective of (valued) quiver up to isomorphism you should allow also index permutations of the c-vectors. The thing I had in mind was quiver isomorphism relative to fixed principal coefficients. In short my suggestion was again bullshit and you should just disregard it.

I am glad that my nonsense somehow lead you to a faster/cleaner implementation anyway.

As for what you say concerning a clean implementation to be added into sage I am
more or less in the same boat as you. I have not used this code in years. The
only thing I currently use of it is the ability to transform various data into
an exchange matrix, afterwards I only use the code we implemented with Dylan. I
might put some effort into reviewing a ticket should it appear but I am not
really motivated to write one myself.

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

9df40f0

working on a cleaner and faster mutation class

[sagetrac-git]

Changed commit from 2bc91b5 to 9df40f0

[stumpc5]

comment:63

I pushed what I currently have, but put this ticket on hold until #24917 is resolved.

[sagetrac-git]

Changed commit from 9df40f0 to 3a1560f

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

3a1560f

playing with a new bliss interface using matrix_to_edge_list

[sagetrac-git]

Changed commit from 3a1560f to c07c97c

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

c07c97c

working on an generic implementation of canonical form for labelled graphs

[stumpc5]

Dependencies: #24924

[sagetrac-git]

Changed commit from c07c97c to b9883f9

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

ff80980	first version of bliss canonical form from edge list
7ea99bd	first version of bliss graph from labelled edges
3f07264	fixed typo, added labelled edge return and fixed bug in relabelling
4661b86	playing the labelled graphs for now
b9883f9	Merge branch 't/24924/making_the_bliss_canonical_form_available_for_edge_labelled_graphs' into t/22381/public/22381

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

97bb60b

merged newest develop

[sagetrac-git]

Changed commit from b9883f9 to 97bb60b

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

c719703

trivial merge

[sagetrac-git]

Changed commit from 97bb60b to c719703