Opened 2 years ago
Last modified 12 months ago
#26771 needs_work enhancement
Implement generalized cluster algebras
Reported by:  ghkelleye  Owned by:  

Priority:  major  Milestone:  
Component:  combinatorics  Keywords:  IMA coding sprints, days99, cluster algebra, generalized cluster algebra, 
Cc:  tscrim, gmoose05, stumpc5, etn40ff, ghEBanaian, drupel  Merged in:  
Authors:  Esther Banaian, Elizabeth Kelley, Dylan Rupel, Gregg Musiker  Reviewers:  
Report Upstream:  N/A  Work issues:  
Branch:  public/ticket26771 (Commits, GitHub, GitLab)  Commit:  4a523cc335bd1b0adc693df3d722b7a32f9d63a7 
Dependencies:  Stopgaps: 
Description (last modified by )
This ticket is being opened to describe proposed work for an coding sprint at the IMA.
In 2011, Chekhov and Shapiro introduced a generalization of cluster algebras in which the exchange polynomials are allowed to have arbitrarily many terms.
We aim to add generalized cluster algebra functionality and related methods necessary to implement the current understanding of these algebras in Sage. This will be accomplished by building upon the framework established by Rupel and Stella's http://doc.sagemath.org/html/en/reference/algebras/sage/algebras/cluster_algebra.html implementation of cluster algebras.
Our major functionality objectives are:
 adding the ability to mutate with arbitrary exchange polynomials to the current ClusterAlgebra? package;
 implementing generalized mutation for coefficients subject to the normalization conditions defined by Tomoki Nakanishi;
 creating methods for calculating left and right companion cluster algebras;
 creating a method for unfolding cluster algebras.
For more information, see:
https://arxiv.org/abs/1111.3963
Attachments (1)
Change History (81)
comment:1 Changed 2 years ago by
 Cc tscrim gmoose05 stumpc5 added
comment:2 Changed 2 years ago by
 Description modified (diff)
comment:3 Changed 2 years ago by
 Cc etn40ff added
 Description modified (diff)
 Milestone changed from sage8.5 to sage8.7
comment:4 Changed 2 years ago by
 Milestone changed from sage8.7 to sage8.8
comment:5 Changed 22 months ago by
 Milestone sage8.8 deleted
As the Sage8.8 release milestone is pending, we should delete the sage8.8 milestone for tickets that are not actively being worked on or that still require significant work to move forward. If you feel that this ticket should be included in the next Sage release at the soonest please set its milestone to the next release milestone (sage8.9).
Changed 21 months ago by
comment:6 Changed 21 months ago by
First step in adding exchange degrees.
comment:7 Changed 21 months ago by
 Cc ghEBanaian added
comment:8 Changed 21 months ago by
 Cc drupel added
comment:9 Changed 21 months ago by
 Branch set to u/ghkelleye/master
Current beta version of the generalized cluster algebra code.
comment:10 Changed 21 months ago by
 Commit set to da5a902eafcb7f511d2bb551fee5c79bd575d9b9
Old attachment can now be ignored.
Last 10 new commits:
816c665  Merge pull request #36 from godfreycw/master

6fee69e  pyflakes cleanup

5bb4e04  Merge pull request #35 from fchapoton/pyflakes

56d9857  trying to tell where conflicts lie

4169540  use splitlines

15a2b7d  Merge pull request #30 from fchapoton/patch1

4034768  Typo: alread > already

2fd52e5  Merge pull request #37 from kevinywlui/patch2

c981690  Actually install the cheat sheet when using setup.py

da5a902  Merge pull request #39 from kevinywlui/develop

comment:11 Changed 21 months ago by
 Branch changed from u/ghkelleye/master to u/gmoose05/master
comment:12 Changed 21 months ago by
 Commit changed from da5a902eafcb7f511d2bb551fee5c79bd575d9b9 to d6c42617c3cc047fb0769899cb5b661b34b8dd5d
Branch pushed to git repo; I updated commit sha1. New commits:
d6c4261  Merge branch 't/26771/master' into develop

comment:13 Changed 21 months ago by
 Commit changed from d6c42617c3cc047fb0769899cb5b661b34b8dd5d to 9d7959f6cf0bf7061c92e5050e4310b6f6518a8d
Branch pushed to git repo; I updated commit sha1. New commits:
9d7959f  Added Exchange Degress for real

comment:14 Changed 21 months ago by
Code rebased for 8.9beta_2  still in testing and debugging phase
comment:15 Changed 21 months ago by
 Branch changed from u/gmoose05/master to u/ghkelleye/master
comment:16 Changed 21 months ago by
 Branch changed from u/ghkelleye/master to u/drupel/master
comment:17 Changed 21 months ago by
 Commit changed from 9d7959f6cf0bf7061c92e5050e4310b6f6518a8d to a903cc865142ec750def5ef5b00560aa5748d7eb
Branch pushed to git repo; I updated commit sha1. New commits:
a903cc8  Updated mutate_initial to compute gvectors and Fpolynomials along the way

comment:18 Changed 21 months ago by
 Commit changed from a903cc865142ec750def5ef5b00560aa5748d7eb to 5aa66f6cac2c6ebd2f44e906e4f4bc8c30963f7a
Branch pushed to git repo; I updated commit sha1. New commits:
5aa66f6  I think mutate_initial works!

comment:19 Changed 21 months ago by
 Commit changed from 5aa66f6cac2c6ebd2f44e906e4f4bc8c30963f7a to 83ba551d6c9552d3199e50af006575db359f0a3f
Branch pushed to git repo; I updated commit sha1. New commits:
83ba551  Fixed mutate_initial (again)

comment:20 Changed 21 months ago by
 Branch changed from u/drupel/master to u/ghkelleye/master
Added some doctests.
comment:21 Changed 21 months ago by
 Branch changed from u/ghkelleye/master to u/gmoose05/master
comment:22 Changed 21 months ago by
 Branch changed from u/gmoose05/master to u/drupel/master
comment:23 Changed 21 months ago by
 Commit changed from 83ba551d6c9552d3199e50af006575db359f0a3f to d5f509ecbfc89082d9848c7f451c8624d0a7cd25
Branch pushed to git repo; I updated commit sha1. New commits:
d5f509e  Small aesthetic fix to mutate_initial

comment:24 Changed 21 months ago by
 Branch changed from u/drupel/master to u/gmoose05/master
comment:25 Changed 21 months ago by
 Commit changed from d5f509ecbfc89082d9848c7f451c8624d0a7cd25 to 7febc08cf41d5006e6f3fd3273779274f1a0cb8a
Branch pushed to git repo; I updated commit sha1. New commits:
7febc08  Placeholder for formal vaariables if intermediate exchange coefficients Z are not specified

comment:26 Changed 21 months ago by
 Commit changed from 7febc08cf41d5006e6f3fd3273779274f1a0cb8a to 0d1920db34a531c102e9f5e13aa19a7af4adee53
Branch pushed to git repo; I updated commit sha1. New commits:
0d1920d  Fixed a few doctests

comment:27 Changed 21 months ago by
 Branch changed from u/gmoose05/master to u/ghkelleye/master
comment:28 Changed 21 months ago by
 Branch changed from u/ghkelleye/master to u/gmoose05/master
comment:29 Changed 21 months ago by
 Branch changed from u/gmoose05/master to u/drupel/master
comment:30 Changed 21 months ago by
 Branch changed from u/drupel/master to u/gmoose05/master
comment:31 Changed 21 months ago by
 Commit changed from 0d1920db34a531c102e9f5e13aa19a7af4adee53 to 7ef4532273916f2807bd576161519ae2525ab75a
Branch pushed to git repo; I updated commit sha1. New commits:
7ef4532  Changed d and Z in ClusterAlgebra to d0 and Z0, and added methods accordingly

comment:32 Changed 21 months ago by
 Commit changed from 7ef4532273916f2807bd576161519ae2525ab75a to 2ec768e4fcc4256c6a8e71a22248b5b40dd11859
comment:33 Changed 21 months ago by
 Commit changed from 2ec768e4fcc4256c6a8e71a22248b5b40dd11859 to a1dd5ec502367fbcfdafca38c102558d41feab82
Branch pushed to git repo; I updated commit sha1. New commits:
a1dd5ec  fixed bug

comment:34 Changed 21 months ago by
 Commit changed from a1dd5ec502367fbcfdafca38c102558d41feab82 to 8fa4c28802d20d6aa82bd3f1518a0708423d7402
Branch pushed to git repo; I updated commit sha1. New commits:
8fa4c28  fixed bug

comment:35 Changed 21 months ago by
 Branch changed from u/gmoose05/master to u/drupel/master
comment:36 Changed 21 months ago by
 Branch changed from u/drupel/master to u/gmoose05/master
comment:37 Changed 21 months ago by
 Branch changed from u/gmoose05/master to u/drupel/master
comment:38 Changed 21 months ago by
 Branch changed from u/drupel/master to u/gmoose05/master
comment:39 Changed 21 months ago by
 Branch changed from u/gmoose05/master to u/drupel/master
comment:40 Changed 21 months ago by
 Branch changed from u/drupel/master to u/gmoose05/master
comment:41 Changed 21 months ago by
 Branch changed from u/gmoose05/master to u/drupel/master
comment:42 Changed 21 months ago by
 Branch changed from u/drupel/master to u/gmoose05/master
comment:43 Changed 21 months ago by
 Branch changed from u/gmoose05/master to u/ghEBanaian/master
comment:44 followup: ↓ 48 Changed 21 months ago by
 Commit changed from 8fa4c28802d20d6aa82bd3f1518a0708423d7402 to 2d80ea706e2830e4542b27f8a8cb9d5538f8afab
 you should rather work with a
public/your_favorite_branch_name
branch, instead of switching all the time
 reference [NR2016] is not defined anywhere
Last 10 new commits:
c37f9bb  Merge branch 'u/gmoose05/master' of git://trac.sagemath.org/sage into t/26771/master

c1bcac5  Edited __init__, cluster variables will not compute in the generalized setting because of coersion issues

a43f77c  added multiplication method for cluster algebra elements

8d98a90  Merge branch 'u/drupel/master' of git://trac.sagemath.org/sage into t/26771/master

10f9fb9  Merge branch 'u/gmoose05/master' of git://trac.sagemath.org/sage into t/26771/master

dc381d5  Attempt fixing variables and coercision

10c71b3  Eliminated nested Laurent polynomial rings

9d6757d  Fixted doctests, added more doctest, only 1 breaking doctest right now (involving sqrt(2) in exchange degree)

f5fcbc7  Updated greedy element to take gen cluster algebras

2d80ea7  Merge branch 'testingJuly11' into t/26771/master

comment:45 Changed 21 months ago by
 Branch changed from u/ghEBanaian/master to u/drupel/master
comment:46 Changed 21 months ago by
 Commit changed from 2d80ea706e2830e4542b27f8a8cb9d5538f8afab to aa3e536cc60f9aecf6f8306da338681a318c6030
 Keywords imacodingsprints sd99 added
New commits:
aa3e536  Minor cleanup in greedy

comment:47 Changed 21 months ago by
 Keywords IMA coding sprints days99 added; imacodingsprints sd99 removed
comment:48 in reply to: ↑ 44 ; followup: ↓ 67 Changed 21 months ago by
Replying to chapoton:
 you should rather work with a
public/your_favorite_branch_name
branch, instead of switching all the time
We are using the automated behavior of the git trac command. Does this command needed to be updated to make the default use "public" as opposed to "user_names", especially when multiple developers are collaborating?
comment:49 Changed 21 months ago by
Well, then forget about git trac and learn to use git. Much better to use git directly imho.
comment:50 Changed 21 months ago by
 Branch changed from u/drupel/master to u/gmoose05/master
comment:51 Changed 21 months ago by
 Commit changed from aa3e536cc60f9aecf6f8306da338681a318c6030 to 5dd29a55b8b8a9693b56a8dc5f94790f6df0cca6
Branch pushed to git repo; I updated commit sha1. New commits:
5dd29a5  Fixed doctests, chose default ground ring to be QQ instead of ZZ to be consistent with Number Field cases

comment:52 Changed 21 months ago by
 Commit changed from 5dd29a55b8b8a9693b56a8dc5f94790f6df0cca6 to 63beddb87ba447efcc7f1ee775e3b7797e302403
Branch pushed to git repo; I updated commit sha1. New commits:
63beddb  Added one more doctest/example

comment:53 Changed 21 months ago by
 Branch changed from u/gmoose05/master to u/ghEBanaian/master
comment:54 Changed 21 months ago by
 Commit changed from 63beddb87ba447efcc7f1ee775e3b7797e302403 to f1c3b8adac19ad53784a7d02f9ad8e413ec6b1f8
Branch pushed to git repo; I updated commit sha1. New commits:
f1c3b8a  doc tests passed

comment:55 Changed 21 months ago by
 Commit changed from f1c3b8adac19ad53784a7d02f9ad8e413ec6b1f8 to 59f9d7bc61fafc2b736a159c9ad8450fd80ae43a
Branch pushed to git repo; I updated commit sha1. New commits:
59f9d7b  Added Doctests to Greedy Element

comment:56 Changed 21 months ago by
 Branch changed from u/ghEBanaian/master to u/ghkelleye/master
Merged changes from ticket 28176.
comment:57 Changed 21 months ago by
 Branch changed from u/ghkelleye/master to u/gmoose05/master
comment:58 Changed 21 months ago by
 Branch changed from u/gmoose05/master to u/ghkelleye/master
comment:59 Changed 21 months ago by
 Branch changed from u/ghkelleye/master to u/gmoose05/master
comment:60 Changed 21 months ago by
 Branch changed from u/gmoose05/master to u/ghkelleye/master
Merged with Sage version 8.9 beta4
comment:61 Changed 21 months ago by
 Commit changed from 59f9d7bc61fafc2b736a159c9ad8450fd80ae43a to 6de458e3be646bfd23685bea481ab19fd47422bd
comment:62 Changed 21 months ago by
 Commit changed from 6de458e3be646bfd23685bea481ab19fd47422bd to f40386e71ef103015db5bbfc4a2ac2798667e5db
Branch pushed to git repo; I updated commit sha1. New commits:
f40386e  Cleaning up comments and doctests. Added references.

comment:63 Changed 21 months ago by
doc still does not build, see comment:44
comment:64 Changed 21 months ago by
 Commit changed from f40386e71ef103015db5bbfc4a2ac2798667e5db to 4732d436daf2608cdf26c655c8c48373f4217b2c
Branch pushed to git repo; I updated commit sha1. New commits:
4732d43  Revised initial comment and added reference

comment:65 Changed 21 months ago by
 Status changed from new to needs_review
comment:66 Changed 21 months ago by
 Branch changed from u/ghkelleye/master to u/gmoose05/master
comment:67 in reply to: ↑ 48 Changed 21 months ago by
 Commit changed from 4732d436daf2608cdf26c655c8c48373f4217b2c to 10d4bca98211f277a1bb9f9f1d05dfca3652c0d9
Replying to gmoose05:
Replying to chapoton:
 you should rather work with a
public/your_favorite_branch_name
branch, instead of switching all the time
We are using the automated behavior of the git trac command. Does this command needed to be updated to make the default use "public" as opposed to "user_names", especially when multiple developers are collaborating?
The default behavior generally assumes one person pushing to a private branch. The solution here is to stop using the default bahavior.
Instead, please run something like:
git trac push branch public/ticket26771 26771
This will set the branch name for the ticket to public/ticket26771
and subsequent pushes will continue to use that upstream branch, rather than constantly switching it between your private branches.
Locally your branch is still yours to work in. It's just when you push/pull that you will have to resolve conflicts, etc.
New commits:
10d4bca  Fixed doctest coverage and removed extraneous imports

comment:68 Changed 21 months ago by
I wasn't aware of that option with git trac push, that's what I was missing. I will use this in the future and if we need further edits for this ticket. Thanks!
comment:69 Changed 21 months ago by
comment:70 Changed 21 months ago by
Dear All,
I would like to be the one giving the final green light to this ticket: it changes quite a lot of the implementation of ClusterAlgebra
so I would prefer to make sure that things still works as expected.
As you know, I am quite busy with my personal life at the moment so please allow me some extra time to process this.
comment:71 Changed 20 months ago by
 Status changed from needs_review to needs_work
red branch, signaling a conflict with the latest beta release
comment:72 Changed 20 months ago by
 Branch changed from u/gmoose05/master to public/ticket26771
comment:73 Changed 20 months ago by
 Commit changed from 10d4bca98211f277a1bb9f9f1d05dfca3652c0d9 to 3ffc9e6c6abca7115f34b3eced6fb755167e518a
 Status changed from needs_work to needs_review
comment:75 Changed 19 months ago by
 Commit changed from 3ffc9e6c6abca7115f34b3eced6fb755167e518a to 4a523cc335bd1b0adc693df3d722b7a32f9d63a7
Branch pushed to git repo; I updated commit sha1. New commits:
4a523cc  Fixed yet another merge conflict in references

comment:76 Changed 19 months ago by
 Status changed from needs_work to needs_review
so back to needs review again, I guess ?
comment:77 Changed 12 months ago by
This has started to bitrot seriously. If nobody takes care of the review, this will be lost work.
comment:78 Changed 12 months ago by
My fault entirely, I got too swamped with other things. Sorry I hope to get to this soon.
comment:79 Changed 12 months ago by
 Status changed from needs_review to needs_work
First of all please accept my apologies for taking so long before reviewing this.
I think that the code in this ticket is far from being ready for a positive review for several reasons.
First of all there is still some debugging scaffolding left over, e.g. at lines just after 1275. This, and any other such, should be removed.
Talking of these lines, is //
really not working? If so this could explain the major
issue I will point out later on.
Second the code introduces a lot of unnecessary small changes like spaces and newlines that make the patch much bigger than it needs to be. Unnecessary white spaces at the end of lines should be avoided. It looks to me that the code here was based on #28176 before it was finalized and therefore it redoes/undoes many of the changes already implemented there. Please remove all of those; ideally this thicket should be rebased on the current develop. I tried doing so but it is not working automagically so someone (else) familiar with the changes should do it.
Similarly the code should be better formatted avoiding long lines and using the correct spacing.
On a more substantial note, the use of both d
and Z
is redundant. I
understand that one wants to allow d
as an input but there is no need to carry
over both of them in the implementation.
Why are you keeping around two copies of the greedy_element framework?
The major obstacle to giving a positive review to this code is the big slowdown it introduces. For example here is the old version in action on my laptop
sage: A = ClusterAlgebra(['E',8],foo=random()) ....: S = A.seeds(mutating_F = False) ....: %time _ = list(S) CPU times: user 21.4 s, sys: 209 ms, total: 21.6 s Wall time: 21.6 s sage: A = ClusterAlgebra(['E',8],foo=random()) ....: %time A.explore_to_depth(infinity) CPU times: user 23.9 s, sys: 191 ms, total: 24.1 s Wall time: 24.1 s
and here is the new one:
sage: A = ClusterAlgebra(['E',8],foo=random()) ....: S = A.seeds(mutating_F = False) ....: %time _ = list(S) CPU times: user 1min 35s, sys: 1.69 s, total: 1min 37s Wall time: 1min 37s
exploring the exchange graph while computing cluster variables with the new code does not terminate in any reasonable amount of time (I killed it after 30 minutes).
I see three possible reasons for this slowdown:
 the algorithms are inherently slower for generalized cluster algebras
 working over symbolic rings is slow
 you are using
/
rather than//
I doubt the reason is the third one since the slowdown appear also when not mutating F_polynomials. The code computing mutations of seeds uses just basic linear algebra and a 400% slowdown in it indicates some major issue.
If the reasons are the first two I would strongly advice to retool this implementation according to this scheme:
 write a base class in which all the common code is located
 add two more classes ClusterAlgebra? and GeneralizedClusterAlgebra? that inherit from the base class
In doing so please make sure that no significant slowdown is introduced in the current code.
comment:80 Changed 12 months ago by
Thanks Salvatore for the detailed report!
There is quite some work to do to try to speed up the divisions because of the symbolic expressions and the exponential growth in terms due to the higher degree exchange polynomials. I am sure that digging into the implementation of polynomial division and carefully sorting terms would eliminate some issues coming from the explosion of terms. More precisely, taking the cluster variables as degree 0 and the exchange coefficients as degree 1 to organize the division should give quite a speed up, but the effort may not be worth the time expense to implement this. Probably retooling as you say at the end is the way to go.
Ticket retargeted after milestone closed (if you don't believe this ticket is appropriate for the Sage 8.8 release please retarget manually)