Implement generalized cluster algebras

[gh-kelleye]

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

​https://arxiv.org/abs/1504.06758

​https://arxiv.org/pdf/1006.4276.pdf

[embray]

Ticket retargeted after milestone closed (if you don't believe this ticket is appropriate for the Sage 8.8 release please retarget manually)

[embray]

As the Sage-8.8 release milestone is pending, we should delete the sage-8.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 (sage-8.9).

[gh-EBanaian]

First step in adding exchange degrees.

[gh-kelleye]

Current beta version of the generalized cluster algebra code.

[gmoose05]

Old attachment can now be ignored.

---

Last 10 new commits:

​816c665	Merge pull request #36 from godfrey-cw/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/patch-1
​4034768	Typo: alread -> already
​2fd52e5	Merge pull request #37 from kevinywlui/patch-2
​c981690	Actually install the cheat sheet when using setup.py
​da5a902	Merge pull request #39 from kevinywlui/develop

[git]

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

​d6c4261

Merge branch 't/26771/master' into develop

[git]

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

​9d7959f

Added Exchange Degress for real

[gmoose05]

Code rebased for 8.9-beta_2 - still in testing and debugging phase

[git]

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

​a903cc8

Updated mutate_initial to compute g-vectors and F-polynomials along the way

[git]

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

​5aa66f6

I think mutate_initial works!

[git]

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

​83ba551

Fixed mutate_initial (again)

[gh-kelleye]

Added some doctests.

[git]

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

​d5f509e

Small aesthetic fix to mutate_initial

[git]

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

​7febc08

Placeholder for formal vaariables if intermediate exchange coefficients Z are not specified

[git]

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

​0d1920d

Fixed a few doctests

[git]

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

[git]

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

​8e067ad	Changed Z in ClusterAlgebra to Z0, and added methods accordingly
​2ec768e	merge

[git]

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

​a1dd5ec

fixed bug

[git]

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

​8fa4c28

fixed bug

[chapoton]

• 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

[gmoose05]

New commits:

​aa3e536

Minor cleanup in greedy

[gmoose05]

Replying to chapoton:

• you should rather work with a public/your_favorite_branch_name branch, instead of switching all the time

• reference [NR2016] is not defined anywhere

---

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?

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

[chapoton]

Well, then forget about git trac and learn to use git. Much better to use git directly imho.

[git]

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

[git]

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

​63beddb

Added one more doctest/example

[git]

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

​f1c3b8a

doc tests passed

[git]

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

​59f9d7b

Added Doctests to Greedy Element

[gh-kelleye]

Merged changes from ticket 28176.

[gh-kelleye]

Merged with Sage version 8.9 beta4

[git]

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

​0eaa1c4	Added comments and doctests for changes related to sd_iter
​6de458e	Cleaned up stray comments

[git]

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

​f40386e

Cleaning up comments and doctests. Added references.

[chapoton]

doc still does not build, see comment:44

[git]

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

​4732d43

Revised initial comment and added reference

[embray]

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/ticket-26771 26771

This will set the branch name for the ticket to public/ticket-26771 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

[gmoose05]

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!

[etn40ff]

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.

[chapoton]

red branch, signaling a conflict with the latest beta release

[chapoton]

so back to needs review, I guess ?

---

New commits:

​3ffc9e6

Fixed merge conflict in references

[chapoton]

red branch again

[git]

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

​4a523cc

Fixed yet another merge conflict in references

[chapoton]

so back to needs review again, I guess ?

[chapoton]

This has started to bit-rot seriously. If nobody takes care of the review, this will be lost work.

[etn40ff]

My fault entirely, I got too swamped with other things. Sorry I hope to get to this soon.

[etn40ff]

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.

[gh-drupel]

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.