Opened 5 years ago
Last modified 4 years ago
#22381 needs_work defect
Bugs in how ClusterQuiver handles coefficients
Reported by:  etn40ff  Owned by:  

Priority:  major  Milestone:  sage8.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, GitHub, GitLab)  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)
Change History (72)
comment:1 Changed 5 years ago by
comment:2 Changed 5 years ago by
 Branch set to public/ticket/22381
 Commit set to 67e6b5b2701488335d0645cc97aeb3d9d2c7bbfc
New commits:
67e6b5b  Add stopgap for trac:22381

comment:3 Changed 5 years ago by
 Branch public/ticket/22381 deleted
 Commit 67e6b5b2701488335d0645cc97aeb3d9d2c7bbfc deleted
comment:4 Changed 5 years ago by
 Stopgaps set to 22464
comment:5 Changed 5 years ago by
 Cc slelievre added
 Stopgaps changed from 22464 to #22464
comment:6 Changed 4 years ago by
 Branch set to u/chapoton/22381
 Commit set to bf0e9502653e856c5201f86ec3b99a406adf190e
 Status changed from new to needs_review
New commits:
bf0e950  trac 22381 do not introduce arrows between frozen vertices

comment:7 Changed 4 years ago by
 Commit changed from bf0e9502653e856c5201f86ec3b99a406adf190e to 4cef3acb8845c0830a103504296637cfc8ddc718
Branch pushed to git repo; I updated commit sha1. New commits:
4cef3ac  another py3related change

comment:8 Changed 4 years ago by
 Component changed from documentation to combinatorics
 Milestone changed from sage7.6 to sage8.2
comment:9 Changed 4 years ago by
 Commit changed from 4cef3acb8845c0830a103504296637cfc8ddc718 to d8358bb4dd42bc48defce33dda551e0885e94783
Branch pushed to git repo; I updated commit sha1. New commits:
d8358bb  other py3 details

comment:10 Changed 4 years ago by
 Commit changed from d8358bb4dd42bc48defce33dda551e0885e94783 to 45607b1c4c90c22785b630a119ae56d3923c6460
Branch pushed to git repo; I updated commit sha1. New commits:
45607b1  another py3 change

comment:11 Changed 4 years ago by
comment:12 Changed 4 years ago by
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 4 years ago by
 Commit changed from 45607b1c4c90c22785b630a119ae56d3923c6460 to ce75cfc8b5ab53eb1aff5cfca59660e4fb20d6da
Branch pushed to git repo; I updated commit sha1. New commits:
ce75cfc  more py3compatibility details

comment:14 Changed 4 years ago by
 Commit changed from ce75cfc8b5ab53eb1aff5cfca59660e4fb20d6da to 01cb2e928a6cf103e7801f8a006b5d95ec32814c
Branch pushed to git repo; I updated commit sha1. New commits:
01cb2e9  yet another py3 enhancement

comment:15 Changed 4 years ago by
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) <ipythoninput1764d1287a18f5> in <module>() > 1 Q.mutation_class() /opt/sage/local/lib/python2.7/sitepackages/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 4 years ago by
 Status changed from needs_review to needs_work
comment:17 Changed 4 years ago by
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 nocoefficients. Always creating a square matrix..
comment:18 Changed 4 years ago by
I just got an email 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 4 years ago by
I think most of the mutation_type and mutation_finite code is made for the coefficientfree 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.
comment:20 Changed 4 years ago by
 Keywords cluster added
comment:21 Changed 4 years ago by
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 4 years ago by
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 4 years ago by
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 caseanalysis 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 4 years ago by
I would suggest moving my branch to another ticket "various enhancements to cluster quivers". Would somebody review that ticket then ?
comment:25 Changed 4 years ago by
"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 4 years ago by
 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 4 years ago by
There remains a few other minor corrections. It would be more complicated to separate them away, as they were in the same commit.
comment:28 Changed 4 years ago by
extracted ticket at #24882
comment:30 Changed 4 years ago by
 Cc jason removed
comment:31 Changed 4 years ago by
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:
 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.
 this is done in
 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 followup: ↓ 33 Changed 4 years ago by
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 4 years ago by
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+m1. 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 followup: ↓ 38 Changed 4 years ago by
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
 starting with a quiver
Q
 taking its b matrix
B
 mutating the b matrix to
B'
 turning
B'
into a new quiverQ'
(observe thatQ
andQ'
largely coincide)  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 4 years ago by
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 4 years ago by
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 ... m1 rather then n ... n+m1). 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 ... n1, n ... n+m1 are currently possible but not supported whatsoever (not going to fix)
comment:37 Changed 4 years ago by
 Commit changed from bf0e9502653e856c5201f86ec3b99a406adf190e to 2bc91b5ef568520f0230c62e0030511a3852f0dd
comment:38 in reply to: ↑ 34 Changed 4 years ago by
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 (coefficientfree) 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 4 years ago by
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.
comment:40 followup: ↓ 42 Changed 4 years ago by
@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 4 years ago by
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 ; followup: ↓ 43 Changed 4 years ago by
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 4 years ago by
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 4 years ago by
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 cvectors (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 4 years ago by
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):
 compute a new object (here using mutation from an old one)
 bring it into a canonical form
 check if you have seen this canonical form before (using a hash table)
 if yes: discard the element
 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 4 years ago by
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 NPhard.
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.
comment:47 Changed 4 years ago by
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 cvectors.
Thm: B1 and B2 in the mutation class of Bp are equivalent if and only if the sets of their cvectors 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 cvectors 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 cvectors 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 followup: ↓ 50 Changed 4 years ago by
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 cvectors 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 cvectors. 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 nonequivalent quivers with principal coefficients, but how does this help to see that their top parts are actually all equivalent?
comment:49 Changed 4 years ago by
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 cvectors). 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 4 years ago by
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 coefficientfree 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 cvectors 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 cvectors. 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 nonequivalent 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 followup: ↓ 52 Changed 4 years ago by
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 4 years ago by
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 cvectors 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 4 years ago by
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 4 years ago by
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 4 years ago by
comment:55 Changed 4 years ago by
I have provided a toy example how to do the mutations on matrices instead at https://trac.sagemath.org/rawattachment/ticket/22381/2018_03CythonTestMatrixMutation.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 4 years ago by
comment:56 Changed 4 years ago by
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_03CythonTestMatrixMutation.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 4 years ago by
(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 4 years ago by
comment:58 Changed 4 years ago by
The newest version https://trac.sagemath.org/attachment/ticket/22381/2018_03CythonTestMatrixMutation.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 followups: ↓ 60 ↓ 61 Changed 4 years ago by
@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 cvectors 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 cvectors 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 cvectors
[(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 4 years ago by
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 cvectors 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 cvectors 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 cvectors
[(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 bmatrix) isomophism types out of this?
comment:61 in reply to: ↑ 59 Changed 4 years ago by
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 cvectors. 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 4 years ago by
 Commit changed from 2bc91b5ef568520f0230c62e0030511a3852f0dd to 9df40f0f1d0524bb532d088736ff16e8772c6240
Branch pushed to git repo; I updated commit sha1. New commits:
9df40f0  working on a cleaner and faster mutation class

comment:63 Changed 4 years ago by
I pushed what I currently have, but put this ticket on hold until #24917 is resolved.
comment:64 Changed 4 years ago by
 Commit changed from 9df40f0f1d0524bb532d088736ff16e8772c6240 to 3a1560f8073b1667c8336b25dd2239e8a62469dc
Branch pushed to git repo; I updated commit sha1. New commits:
3a1560f  playing with a new bliss interface using matrix_to_edge_list

comment:65 Changed 4 years ago by
 Commit changed from 3a1560f8073b1667c8336b25dd2239e8a62469dc to c07c97ca7b9037e3dc9610953f9b02eaadd1a878
Branch pushed to git repo; I updated commit sha1. New commits:
c07c97c  working on an generic implementation of canonical form for labelled graphs

comment:66 Changed 4 years ago by
 Dependencies set to #24924
comment:67 Changed 4 years ago by
 Commit changed from c07c97ca7b9037e3dc9610953f9b02eaadd1a878 to b9883f99e49ef533e3bf7524e4b0eb5ddcf03699
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

comment:68 Changed 4 years ago by
 Commit changed from b9883f99e49ef533e3bf7524e4b0eb5ddcf03699 to 97bb60b7fb7383325f88f55152fd0e2aaa6bbaac
Branch pushed to git repo; I updated commit sha1. New commits:
97bb60b  merged newest develop

comment:69 Changed 4 years ago by
 Commit changed from 97bb60b7fb7383325f88f55152fd0e2aaa6bbaac to c719703f400e7076e5b3d9489a56cfdf2ebc53dd
Branch pushed to git repo; I updated commit sha1. New commits:
c719703  trivial merge

Actually a better example for the third issue: