Opened 4 years ago

Last modified 2 years ago

#22381 needs_work defect

Bugs in how ClusterQuiver handles coefficients

Reported by: etn40ff Owned by:
Priority: major Milestone: sage-8.2
Component: combinatorics Keywords: ClusterSeed, mutations, cluster
Cc: gmoose05, stumpc5, drupel, vpilaud, slelievre Merged in:
Authors: Frédéric Chapoton Reviewers:
Report Upstream: N/A Work issues:
Branch: public/22381 (Commits) Commit: c719703f400e7076e5b3d9489a56cfdf2ebc53dd
Dependencies: #24924 Stopgaps: #22464

Description

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

Attachments (3)

2018_03-CythonTestMatrixMutation.py (4.7 KB) - added by stumpc5 3 years ago.
2018_03-CythonTestMatrixMutation.2.py (3.8 KB) - added by stumpc5 3 years ago.
2018_03-CythonTestMatrixMutation.3.py (4.0 KB) - added by stumpc5 3 years ago.

Download all attachments as: .zip

Change History (72)

comment:1 Changed 4 years ago by etn40ff

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

comment:2 Changed 4 years ago by etn40ff

  • Branch set to public/ticket/22381
  • Commit set to 67e6b5b2701488335d0645cc97aeb3d9d2c7bbfc

New commits:

67e6b5bAdd stopgap for trac:22381

comment:3 Changed 4 years ago by etn40ff

  • Branch public/ticket/22381 deleted
  • Commit 67e6b5b2701488335d0645cc97aeb3d9d2c7bbfc deleted

comment:4 Changed 4 years ago by etn40ff

  • Stopgaps set to 22464

comment:5 Changed 4 years ago by slelievre

  • Cc slelievre added
  • Stopgaps changed from 22464 to #22464

comment:6 Changed 3 years ago by chapoton

  • Branch set to u/chapoton/22381
  • Commit set to bf0e9502653e856c5201f86ec3b99a406adf190e
  • Status changed from new to needs_review

New commits:

bf0e950trac 22381 do not introduce arrows between frozen vertices

comment:7 Changed 3 years ago by git

  • Commit changed from bf0e9502653e856c5201f86ec3b99a406adf190e to 4cef3acb8845c0830a103504296637cfc8ddc718

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

4cef3acanother py3-related change

comment:8 Changed 3 years ago by chapoton

  • Component changed from documentation to combinatorics
  • Milestone changed from sage-7.6 to sage-8.2

comment:9 Changed 3 years ago by git

  • Commit changed from 4cef3acb8845c0830a103504296637cfc8ddc718 to d8358bb4dd42bc48defce33dda551e0885e94783

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

d8358bbother py3 details

comment:10 Changed 3 years ago by git

  • Commit changed from d8358bb4dd42bc48defce33dda551e0885e94783 to 45607b1c4c90c22785b630a119ae56d3923c6460

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

45607b1another py3 change

comment:11 Changed 3 years ago by chapoton

  • Authors set to Frédéric Chapoton

comment:12 Changed 3 years ago by etn40ff

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.

comment:13 Changed 3 years ago by git

  • Commit changed from 45607b1c4c90c22785b630a119ae56d3923c6460 to ce75cfc8b5ab53eb1aff5cfca59660e4fb20d6da

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

ce75cfcmore py3-compatibility details

comment:14 Changed 3 years ago by git

  • Commit changed from ce75cfc8b5ab53eb1aff5cfca59660e4fb20d6da to 01cb2e928a6cf103e7801f8a006b5d95ec32814c

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

01cb2e9yet another py3 enhancement

comment:15 Changed 3 years ago by etn40ff

I finally managed to recompile sage and I gave a quick spin to this patch. Something seems to be still wrong as it still fails on type A_2 cluster algebras:

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()
---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
<ipython-input-17-64d1287a18f5> in <module>()
----> 1 Q.mutation_class()

/opt/sage/local/lib/python2.7/site-packages/sage/combinat/cluster_algebra_quiver/quiver.pyc in mutation_class(self, depth, show_depth, return_paths, data_type, up_to_equivalence, sink_source)
   1883         """
   1884         if depth is infinity and not self.is_mutation_finite():
-> 1885             raise ValueError('the mutation class can - for infinite mutation'
   1886                              ' types - only be computed up to a given depth')
   1887         return [Q for Q in self.mutation_class_iter(depth=depth, show_depth=show_depth,

ValueError: the mutation class can - for infinite mutation types - only be computed up to a given depth

While having a look I could not avoid asking myself what is the point of _digraph_mutate. It sounds like an extremely convoluted way of performing mutations. Dealing with matrices instead should be as simple as

def mutate(B, k):
    m = B.nrows()
    n = B.ncols()
    M = matrix(m,n, lambda i,j: -B[i,j] if i==k or j==k else B[i,j] + (abs(B[i,k])*B[k,j] + B[i,k]*abs(B[k,j]))/2 )
    return M

Is there any speed advantage in dealing with digraphs? Can some of the original contributors please comment on this point?

comment:16 Changed 3 years ago by etn40ff

  • Status changed from needs_review to needs_work

comment:17 Changed 3 years ago by chapoton

It seems that _digraph_to_dig6 and _dig6_to_digraph in sage.combinat.cluster_algebra_quiver.mutation_class are only dealing seriously with the case of no-coefficients. Always creating a square matrix..

comment:18 Changed 3 years ago by etn40ff

I just got an e-mail from Gregg. He basically says that the point of digraph is to be able to label the vertices. Other than that matrices should be sufficient and faster.

The only other things that comes to mind is that Christian might have done some optimization to identify mutation classes and this might be based on digraphs. It is probably the cheapest way to check for isomorphism of (valued) quivers. Should we ask him explicitly to comment on this?

My impression is that there are now two competing codebases for doing mutations, one with graphs and one with matrices, that somehow are simultaneously in ClusterQuiver there should be quite a lot of room for cleanup. This does not sound like a short term project though.

comment:19 Changed 3 years ago by chapoton

I think most of the mutation_type and mutation_finite code is made for the coefficient-free case and will be hard work to update. Even in your example of type A3 with coeffs, after being convinced to start mutating, it seems to find an infinite number of quivers...

I would suggest:

(1) close this ticket with the improvements it brings, including progress towards py3

(2) open another one for the mutation type and finiteness issues.

Last edited 3 years ago by chapoton (previous) (diff)

comment:20 Changed 3 years ago by chapoton

  • Keywords cluster added

comment:21 Changed 3 years ago by etn40ff

I agree this is not going to be a quick fix and there is no point in delaying py3. The only thing is that we should really make sure that the stopgap #22464 is also updated to the new ticket.

comment:22 Changed 3 years ago by stumpc5

Hi,

this whole code clusterseed / quiver code seems to be a disaster, I wonder how much of it was actually broken from my first version of its code -- sorry at least for these originally broken parts!

Is there any speed advantage in dealing with digraphs? Can some of the original contributors please comment on this point?

I have certainly spent a lot of time optimizing mutations, and used matrix mutation written in cython whereever possible. I believe, I have even used this for quiver mutations, but I am not totally sure.

I will try to give a slightly more informative comment tomorrow, hopefully after I had a look at the original code...

comment:23 Changed 3 years ago by stumpc5

Okay, it seems that the quiver code is indeed broken for frozen variables since a long time, maybe even from the beginning (we wrote the code initially without frozen variables), and we even used _digraph_mutate from the beginning. I don't see any reason for using _digraph_mutate but I don't recall why we used it in the first place either.

The b matrix mutation is cythonized from the beginning and was then as fast as possible, see the mutate method matrix/matrix0.pyx: def mutate(self, Py_ssize_t k ).

I think I agree that digraph_to_dig6 and dig6_to_digraph only deal with no coefficients. I actually don't think this is used at all in practice. Originally it is used to store mutation classes of quivers without coefficients for faster type recognition (and there, one never deals with coefficients).

The type recognition for seeds and quivers is done by taking the quiver without coefficients and determining its type by a nightmare case-analysis algorithm (I wrote it and knew from the beginning that it will be impossible to properly debug or understand, but it worked for all types...).

The mutation_class_iter method seems to be a horrible code duplication, done either for quivers (where _digraph_mutate is used in mutation_class line 253) or for seeds (where matrix mutation is used in cluster_seed line 3566).

I would suggest to fix the broken quiver mutation method, and then first run tests if that fixes the issues with quivers, or if there are any further issues. And only then start improving the code, if desired -- though I had in mind that Salvatore's new stuff is anyway much better from all perspectives...

comment:24 Changed 3 years ago by chapoton

I would suggest moving my branch to another ticket "various enhancements to cluster quivers". Would somebody review that ticket then ?

comment:25 Changed 3 years ago by stumpc5

"various enhancements to cluster quivers"

I will do a review of the code you provided. In principle, I find it much simpler to review changes that only have a single purpose, so having the formatting and py3 changes separated from the changes to the quiver mutation.

I would suggest, you move all formatting changes into another ticket which could go directly, and keep the actual behaviour modifications to _digraph_mutate so I can have a closer look at these and see how fixing the mutation issue there also fixes other issues we encountered.

comment:26 Changed 3 years ago by chapoton

  • Branch changed from u/chapoton/22381 to public/22381
  • Commit changed from 01cb2e928a6cf103e7801f8a006b5d95ec32814c to bf0e9502653e856c5201f86ec3b99a406adf190e

Here is a branch only changing _digraph_mutate. It DOES NOT fix any issue concerning mutation type and mutation finiteness.

comment:27 Changed 3 years ago by chapoton

There remains a few other minor corrections. It would be more complicated to separate them away, as they were in the same commit.

Last edited 3 years ago by chapoton (previous) (diff)

comment:28 Changed 3 years ago by chapoton

extracted ticket at #24882

comment:29 Changed 3 years ago by chapoton

  • Cc jason added

EDIT: wrong ticket, sorry

Last edited 3 years ago by chapoton (previous) (diff)

comment:30 Changed 3 years ago by chapoton

  • Cc jason removed

comment:31 Changed 3 years ago by stumpc5

I will post here whatever I encounter in the code, so that I keep track of what I understand, and for others to read and comment on.

The only other things that comes to mind is that Christian might have done some optimization to identify mutation classes and this might be based on digraphs.

The big issue is that we consider quivers often as unlabelled graphs, see the up_to_equivalence=True flag in mutation_class._mutation_class_iter.

There are thus multiple issues to keep track of:

  1. getting quivers into canonical form (by relabelling the vertices into a canonical ordering) and mutate at as least as possible vertices:
    • this is done in _dg_canonical_form, where the input quiver is put into a canonical form, while the relabelling of the vertices and the orbits of vertices under the isomorphism group is also collected.
    • this done, we only need to mutate at one vertex per orbit, and keep track that of the relabelling.
  1. checking if we already have encountered a given quiver.
    • this is done using its dig6 string because checking if a string is contained in a set of strings is infinitely much faster than checking if a digraph is contained in a set/list of digraphs.

None of this was ever properly done for using frozen vertices.

@Frederic: am i correct that you now properly do the mutation with frozen vertices in _digraph_mutate ?

I hope things will work out again once also the dig6 stuff is properly updated what I will do now.

comment:32 follow-up: Changed 3 years ago by chapoton

NOTE: I assumed in my changes that the frozen vertices are always the final one, labelled from n+1 to n+m. I am unsure if this is always the case.

comment:33 in reply to: ↑ 32 Changed 3 years ago by stumpc5

Replying to chapoton:

NOTE: I assumed in my changes that the frozen vertices are always the final one, labelled from n+1 to n+m. I am unsure if this is always the case.

same here, I also just wondered if we can even assume the vertex labellings to be integers or numbers 0 through n+m-1. I really don't know how all this changed. The attributes Q._nlist and Q._mlist might suggest that other vertex labellings are possible.

comment:34 follow-up: Changed 3 years ago by stumpc5

The reason to use _digraph_mutate over matrix mutation is that the canonical form algorithm

    from sage.groups.perm_gps.partn_ref.refinement_graphs import search_tree, get_orbits

takes a digraph, so

  1. starting with a quiver Q
  2. taking its b matrix B
  3. mutating the b matrix to B'
  4. turning B' into a new quiver Q' (observe that Q and Q' largely coincide)
  5. computing the canonical form of Q'

is much slower (especially for large quivers where the coincidence in 4. is even bigger) than directly doing the digraph mutation.

Observe that the actual mutation is indeed much faster on matrices, so having an equally fast version of the canonical form directly on matrices (take a square matrix and bring it into a canonical form up to simultaneous row- and column permutations) would be also solving the problem.

comment:35 Changed 3 years ago by stumpc5

Given

sage: D = ClusterQuiver(['A',2])._digraph
sage: D.relabel({0:"A",1:frozenset([1,2,"A"])})
sage: ClusterQuiver(D)._digraph.edges()
[('A', frozenset({1, 2, 'A'}), (1, -1))]

I must say that I am not willing to take this into account. I believe that _digraph should always be a digraph with vertices range(n+m) with mutable vertices range(n) and frozen vertices range(n+1,n+m) (*).

I believe this extra layer should be handled separately at a "high level" and not changing the backend algorithms of quivers. All mutation class and mutation type code is written with this assumption (*).

comment:36 Changed 3 years ago by stumpc5

Okay, there are plenty of errors, I have fixed a few, but cannot push currently:

  • ClusterQuiver.canonical_label has an obvious bug for frozen variables (it froze variables 0 ... m-1 rather then n ... n+m-1). fixed.
  • _digraph_mutate still makes mistakes:
    sage: Q = ClusterQuiver(['B',2]).principal_extension()
    sage: Q.mutate(0)
    sage: Q.b_matrix()
    [ 0 -1]
    [ 2  0]
    [-1  1]
    [ 0  1]
    sage: Q._digraph.edges(labels=True)
    [(0, 2, (1, -1)), (1, 0, (2, -1)), (2, 1, (1, -2)), (3, 1, (1, -1))]
    

The label for (2,1) should be (1,-1) if I see it correctly. (not fixed)

  • the dig6 conversion is broken (not fixed)
  • finally, vertices of the digraph different from 0 ... n-1, n ... n+m-1 are currently possible but not supported whatsoever (not going to fix)

comment:37 Changed 3 years ago by git

  • Commit changed from bf0e9502653e856c5201f86ec3b99a406adf190e to 2bc91b5ef568520f0230c62e0030511a3852f0dd

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

e0302f7cosmetical changes
2bc91b5fixed ClusterQuiver.canonical_label

comment:38 in reply to: ↑ 34 Changed 3 years ago by etn40ff

Replying to stumpc5:

Observe that the actual mutation is indeed much faster on matrices, so having an equally fast version of the canonical form directly on matrices (take a square matrix and bring it into a canonical form up to simultaneous row- and column permutations) would be also solving the problem.

What about the following for a canonical form of a (coefficient-free) exchange matrix?

1) take the columns of B and sort each of them

2) sort the resulting lists lexicographically

3) 2 gives a permutation, use this permutation on rows and columns of B

To compare matrices in the canonical form you can then just use hashes.

comment:39 Changed 3 years ago by stumpc5

I did a few tests if it is possible to do the quiver mutation using matrices, and I got

sage: %timeit M.mutate(1)
100000 loops, best of 3: 2.77 µs per loop
sage: %timeit _digraph_mutate(D,1,5,5)
10000 loops, best of 3: 37.8 µs per loop
sage: %timeit digraph_mutate_new(D,1,5,5)
The slowest run took 611.92 times longer than the fastest. This could mean that an intermediate result is being cached.
10000 loops, best of 3: 59.2 µs per loop

The later turns the digraph into a matrix and back in cython, and I don't see how to improve this my much since the time is almost completely spend in reading the edges of the input graph, creating the matrix, and writing the output graph.

Last edited 3 years ago by stumpc5 (previous) (diff)

comment:40 follow-up: Changed 3 years ago by stumpc5

@Salvatore: canonical form is up to simultaneous row and column permutation, not up to row and column permutation! This canonical form in particular solves graph isomorphism (two graphs are isomorphic if and only if their canonical form adjacency matrices coincide, observe that a simultaneous row and column permutation is a relabelling of the vertices of the graph) and the later is implemented and highly optimized in sage.

There is no chance to provide anything speedwise comparable directly on matrices without reimplementing the above algorithm, I did quite some tests when implementing it and the outcome was that graph canonical form is by far fastest available.

comment:41 Changed 3 years ago by stumpc5

To compare matrices in the canonical form you can then just use hashes.

well, on the level of the graphs, the dig6 string is basically the (invertible) hash, though you might be right that an ordinary hash might be faster and also working. I will recheck...

comment:42 in reply to: ↑ 40 ; follow-up: Changed 3 years ago by etn40ff

Replying to stumpc5:

@Salvatore: canonical form is up to simultaneous row and column permutation, not up to row and column permutation! This canonical form in particular solves graph isomorphism (two graphs are isomorphic if and only if their canonical form adjacency matrices coincide, observe that a simultaneous row and column permutation is a relabelling of the vertices of the graph) and the later is implemented and highly optimized in sage.

There is no chance to provide anything speedwise comparable directly on matrices without reimplementing the above algorithm, I did quite some tests when implementing it and the outcome was that graph canonical form is by far fastest available.

I think you misunderstood the algorithm I was suggesting: 3 would be applied to rows and columns of B simultaneously, not to the sorted vectors in 2.

In any case I think I was being stupid for other reasons: the algorithm proposed basically sorts vertices according to their in and out degrees (or actually some finer version of this where we keep track of how many arrows from distinct vertices are adjacent to each node). This is not enough information to distinguish any two quivers. The first example that comes to mind is a "figure 8 quiver" with one vertex of degree 4 (2 in and 2 out) and 4 vertices of degree 2 (1 in and 1 out). The algorithm I had in mind can't distinguish the case with a 3 cycle attached to a 5 cycle from the case of two 4 cycles glued together.

Sorry about the stupid remark.

comment:43 in reply to: ↑ 42 Changed 3 years ago by stumpc5

Replying to etn40ff:

I think you misunderstood the algorithm I was suggesting: 3 would be applied to rows and columns of B simultaneously, not to the sorted vectors in 2.

Oh yes, I did, sorry. Anyway, highly optimized graph canonical form algorithms are hard to beat with an algorithm that in particular solves graph canonical form...

comment:44 Changed 3 years ago by etn40ff

Stern but just :D

Since this is my day for random stupid ideas here is another. Can't we use CAIV to speed up the process? It is known that the exchange graph associated to any quiver with any choice of coefficients is a quotient of the exchange graph associated to the same quiver but with principal coefficients.

Can we just pretend we always have principal coefficients(by artificially adding them) and then perform mutations on the matrices only? Deciding if two seeds coincide is just a matter of comparing the associated lists of c-vectors (and this is fast). If we care about the up to equivalence case we can always check for graph isomorphisms in a second time.

I am basically proposing to replace code duplication and digraphs with possibly more mutations but performed much faster.

This is what me and Dylan do in ClusterAlgebra but there we never care about the up to equivalence issue.

comment:45 Changed 3 years ago by stumpc5

I am not sure I really follow how you want to do the check.

Please let me note that we want to list all quivers up to equivalence. The best way approach I know of is the following much more general algorithm using a canonical form (where two objects are considered equivalent if they have the same canonical form):

  1. compute a new object (here using mutation from an old one)
  2. bring it into a canonical form
  3. check if you have seen this canonical form before (using a hash table)
  4. if yes: discard the element
  5. if no: store the canonical form in the hash table, and keep the element.

Observe that you must in particular compute the canonical form for each element you encounter.

I don't see how you could bypass this canonical form computation. In particular, I don't see how your approach could deal with this other than also computing it.

comment:46 Changed 3 years ago by stumpc5

You are more than welcome to try to beat the current algorithm!

  • I am sure that you will be able to do so if you spend enough time and thinking.
  • I am certainly willing to help you with this.

I would personally expect that the optimal reachable solution is to generalize the graph canonical form to a matrix canonical form. Citation from https://en.wikipedia.org/wiki/Graph_canonization:

A commonly known canonical form is the lexicographically smallest graph within the isomorphism class, which is the graph of the class with lexicographically smallest adjacency matrix considered as a linear string. However, the computation of the lexicographically smallest graph is NP-hard.

We currently use sage.groups.perm_gps.partn_ref.refinement_graphs.search_tree which implements McKay - Practical Graph Isomorphism, see in particular https://arxiv.org/abs/1301.1493.

Last edited 3 years ago by stumpc5 (previous) (diff)

comment:47 Changed 3 years ago by etn40ff

Ok, let me try to explain a little better if I can. Suppose that we have a square exchange matrix B and consider its its principal framing Bp (i.e. B with the identity matrix attached to the bottom). Suppose for a moment that we want to list all the matrices in the mutation class of Bp up to simultaneous permutations of columns and (the first n) rows.

Call the columns of the bottom part of a matrix obtained by mutations from Bp its c-vectors.

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

So here is the algorithm to list all the matrices mutationally equivalent to Bp: Start from Bp and perform mutations, at each step compare the set of c-vectors with the one already known. This completely solve the problem in the case of principal coefficients and is much faster than any other implementation using digraphs and canonical forms for comparisons.

Suppose now that Bf is any other rectangular matrix with the same B as the top part. Suppose that B1f is obtained from Bf by a certain sequence of mutations and suppose that B1 is obtained from Bp with the same sequence of mutations. Then, obviously, the top part of B1f and B1 coincide. Moreover there is a transformation (that depends only on Bf so it applies to the entire mutation class) that expresses the bottom part of B1f in terms of the c-vectors of B1. In particular if B1 and B2 are equivalent so do B1f and B2f for any choice of framing.

It remains to test the situation in which B1 and B2 are distinct but have equivalent top parts to see if B1f and B2f are equivalent. For cluster algebras this is an irrelevant issue and we just do not care in our implementation. Indeed the only relevant framing for the combinatorial structure of a cluster algebra is the principal one.

If one is only interested in quiver mutations it could be relevant. In any case it should be faster to compare using digraphs only the matrices the previous algorithm produce rather than all of them.

In short: to compute mutation classes we do not need to solve the graph isomorphism problem in full generality.

comment:48 follow-up: Changed 3 years ago by stumpc5

This completely solve the problem in the case of principal coefficients and is much faster than any other implementation using digraphs and canonical forms for comparisons.

This might be correct, but is not totally obvious. The canonical form tells which vertices are equivalent, so we do not need to mutate all, but only one per equivalence class of vertices (orbits of the isomorphism group).

Moreover there is a transformation (that depends only on Bf so it applies to the entire mutation class) that expresses the bottom part of B1f in terms of the c-vectors of B1. In particular if B1 and B2 are equivalent so do B1f and B2f for any choice of framing.

I see this, but don't we rather also need the other direction, since we want to solve isomorphism for Bf? Imagine Bf is only the top part, so there are no c-vectors. We now need to check isomorphism for Bf? Could you apply your algorithm (for me to understand) to find the unique quiver of type A2, and an example of how to find the four quivers of type A3? (In the first case, you first find 5 quivers starting with principal coefficients, and in the second you find 14 -- and I fail to see how these are reduced to 1 and 4, resp.)

If one is only interested in quiver mutations it could be relevant.

Isn't this complete thread and the algorithm about quiver mutations and not about cluster seed mutations? If I see your algorithm correctly, it would find the five non-equivalent quivers with principal coefficients, but how does this help to see that their top parts are actually all equivalent?

comment:49 Changed 3 years ago by stumpc5

You can see in ClusterSeed.mutation_class_iter that we do not do any graph isomorphism there and compare the cluster variables (instead of your c-vectors). We also perform matrix mutation in this case and no digraph mutation. What I thought we discuss in this thread is quiver mutation and quiver mutation class computations.

comment:50 in reply to: ↑ 48 Changed 3 years ago by etn40ff

Replying to stumpc5:

This completely solve the problem in the case of principal coefficients and is much faster than any other implementation using digraphs and canonical forms for comparisons.

This might be correct, but is not totally obvious. The canonical form tells which vertices are equivalent, so we do not need to mutate all, but only one per equivalence class of vertices (orbits of the isomorphism group).

Some tests of the current versions of ClusterQuiver for the coefficient-free case (because I could not make the general case run) and ClusterAlgebraSeed with principal coefficients

sage: A = ClusterAlgebra(['D',10], principal_coefficients=True)
sage: %time _ = list(A.seeds(mutating_F=False))
CPU times: user 1min 25s, sys: 525 ms, total: 1min 25s
Wall time: 1min 25s
sage: Q = ClusterQuiver(['D',10])
sage: %time _ = list(Q.mutation_class_iter())
CPU times: user 1min 18s, sys: 64.5 ms, total: 1min 18s
Wall time: 1min 18s

show that the two are comparable in finite types. Actually implementing what I suggest is worse because then one has to further reduce the output according to coeffieicents. I do not know how well ClusterQuiver scales as the number of coefficients grows (assuming we can make it work).

Beyond finite types things are different because there are not as many symmetries. For example

sage: B = matrix(10, lambda i,j: 1 if random() <0.5 else 0)
sage: B -= B.transpose()
sage: Q = ClusterQuiver(B)
sage: mut_class = Q.mutation_class_iter()
sage: count = 0
sage: %time while count < 100000: _ = mut_class.next(); count +=1
CPU times: user 3min 32s, sys: 13.7 ms, total: 3min 32s
Wall time: 3min 33s
sage: A = ClusterAlgebra(B)
sage: mut_class = A.seeds(mutating_F=False)
sage: count = 0
sage: %time while count < 100000: _ = mut_class.next(); count +=1
CPU times: user 51.4 s, sys: 491 ms, total: 51.9 s
Wall time: 52.1 s

Moreover there is a transformation (that depends only on Bf so it applies to the entire mutation class) that expresses the bottom part of B1f in terms of the c-vectors of B1. In particular if B1 and B2 are equivalent so do B1f and B2f for any choice of framing.

I see this, but don't we rather also need the other direction, since we want to solve isomorphism for Bf? Imagine Bf is only the top part, so there are no c-vectors. We now need to check isomorphism for Bf? Could you apply your algorithm (for me to understand) to find the unique quiver of type A2, and an example of how to find the four quivers of type A3? (In the first case, you first find 5 quivers starting with principal coefficients, and in the second you find 14 -- and I fail to see how these are reduced to 1 and 4, resp.)

Just run the same algorithm you run now: digraph isomorphism. In this example you point out my suggestion is way more expensive than the one you implemented: I have to find 5 quivers and then test all of them to see that they coincide. On a not so symmetric case though my approach could save quite some time.

If one is only interested in quiver mutations it could be relevant.

Isn't this complete thread and the algorithm about quiver mutations and not about cluster seed mutations? If I see your algorithm correctly, it would find the five non-equivalent quivers with principal coefficients, but how does this help to see that their top parts are actually all equivalent?

I am just saying we could consider the possibility to derive the algorithm for quivers out of the algorithm for cluster algebras with (possibly?) a speedup. Of course I am not even sure this is worth doing.

comment:51 follow-up: Changed 3 years ago by 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?

comment:52 in reply to: ↑ 51 Changed 3 years ago by etn40ff

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.

comment:53 Changed 3 years ago by stumpc5

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...

comment:54 Changed 3 years ago by etn40ff

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.

Changed 3 years ago by stumpc5

comment:55 Changed 3 years ago by stumpc5

I have provided a toy example how to do the mutations on matrices instead at https://trac.sagemath.org/raw-attachment/ticket/22381/2018_03-CythonTestMatrixMutation.py.

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?

Changed 3 years ago by stumpc5

comment:56 Changed 3 years ago by stumpc5

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

comment:57 Changed 3 years ago by stumpc5

(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.)

Changed 3 years ago by stumpc5

comment:58 Changed 3 years ago by stumpc5

The newest version https://trac.sagemath.org/attachment/ticket/22381/2018_03-CythonTestMatrixMutation.3.py 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.

comment:59 follow-ups: Changed 3 years ago by 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).

comment:60 in reply to: ↑ 59 Changed 3 years ago by stumpc5

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?

comment:61 in reply to: ↑ 59 Changed 3 years ago by etn40ff

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.

comment:62 Changed 3 years ago by git

  • Commit changed from 2bc91b5ef568520f0230c62e0030511a3852f0dd to 9df40f0f1d0524bb532d088736ff16e8772c6240

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

9df40f0working on a cleaner and faster mutation class

comment:63 Changed 3 years ago by stumpc5

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

comment:64 Changed 3 years ago by git

  • Commit changed from 9df40f0f1d0524bb532d088736ff16e8772c6240 to 3a1560f8073b1667c8336b25dd2239e8a62469dc

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

3a1560fplaying with a new bliss interface using matrix_to_edge_list

comment:65 Changed 3 years ago by git

  • Commit changed from 3a1560f8073b1667c8336b25dd2239e8a62469dc to c07c97ca7b9037e3dc9610953f9b02eaadd1a878

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

c07c97cworking on an generic implementation of canonical form for labelled graphs

comment:66 Changed 3 years ago by stumpc5

  • Dependencies set to #24924

comment:67 Changed 3 years ago by git

  • Commit changed from c07c97ca7b9037e3dc9610953f9b02eaadd1a878 to b9883f99e49ef533e3bf7524e4b0eb5ddcf03699

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

ff80980first version of bliss canonical form from edge list
7ea99bdfirst version of bliss graph from labelled edges
3f07264fixed typo, added labelled edge return and fixed bug in relabelling
4661b86playing the labelled graphs for now
b9883f9Merge branch 't/24924/making_the_bliss_canonical_form_available_for_edge_labelled_graphs' into t/22381/public/22381

comment:68 Changed 3 years ago by git

  • Commit changed from b9883f99e49ef533e3bf7524e4b0eb5ddcf03699 to 97bb60b7fb7383325f88f55152fd0e2aaa6bbaac

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

97bb60bmerged newest develop

comment:69 Changed 2 years ago by git

  • Commit changed from 97bb60b7fb7383325f88f55152fd0e2aaa6bbaac to c719703f400e7076e5b3d9489a56cfdf2ebc53dd

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

c719703trivial merge
Note: See TracTickets for help on using tickets.