Cythonize quiver paths

[simon-king-jena]

Currently, sage.quivers.paths is Python code and rather slow. The purpose of this ticket is to provide a speed-up, using "bounded integer sequences" introduced at #15820.

Depends on #15820 Depends on #17564

CC: @nthiery @nathanncohen @stumpc5 @saliola

Component: algebra

Author: Simon King

Branch: 3c4c54a

Reviewer: Vincent Delecroix

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

[simon-king-jena]

Description changed:

--- 
+++ 
@@ -1 +1 @@
-
+Currently, `sage.quivers.paths` is Python code and rather slow. The purpose of this ticket is to provide a speed-up, using "bounded integer sequences" introduced at #15820.

[simon-king-jena]

Dependencies: 15820

[simon-king-jena]

Branch: u/SimonKing/cythonize_quiver_paths

[simon-king-jena]

Commit: ab27a4c

[simon-king-jena]

Last 10 new commits:

64ac7ba	Pickling of bounded integer sequence. Documentation of cdef functions
050b118	Improve access to items of bounded integer sequences
c2e3547	Improve conversion "list->bounded integer sequence"
836f63f	Improve iteration and list/string conversion of bounded integer sequences
c8a299b	More documentation of bounded integer sequences
775d795	Improve index computation for bounded integer sequences
391a102	Improve bounded integer subsequent containment test
735939e	Improve slicing of bounded integer sequences
c900a2c	Take care of GMP's removal of trailing zeroes
ab27a4c	Merge branch 'u/SimonKing/ticket/15820' of trac.sagemath.org:sage into t/16453/cythonize_quiver_paths

[simon-king-jena]

Changed dependencies from 15820 to #15820

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

b22a570	Initial cythoned version of quiver paths
1192c21	Allow empty slices; bounded integer sequence -> bool
ef2c812	Merge branch 'u/SimonKing/ticket/15820' of trac.sagemath.org:sage into t/16453/cythonize_quiver_paths
54482aa	Making cythoned quiver paths work

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from ab27a4c to 54482aa

[simon-king-jena]

comment:5

I have provided a cythoned version of quiver paths (i.e., elements of path semigroups), based on the bounded integer sequences of #15820. All tests pass, so, needs review.

I didn't do timings yet. And hopefully it is ok that I slightly changed the syntax to create a path:

   old                       new
Q((1,1))                  Q([(1,1)])
Q([(1,2,'a'), (2,3,'b')]  Q(['a','b'])  # old syntax still works
Q((1,2,'a'))              Q([(1,2,'a')]) or Q('a')

[simon-king-jena]

Author: Simon King

[simon-king-jena]

comment:7

I think I should also provide something like a gcd for paths. This is likely to be implemented as a function in sage.misc.bounded_integer_sequences computing the largest overlap between two sequences S1, S2, i.e.: largest_overlap(S1,S2) is the smallest number i such that S2 starts with S1[i:]. This is something that will obviously be relevant when implementing Gröbner bases for path algebras.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 54482aa to 7964292

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

ff4477a	Remove biseq_to_str. Add max_overlap. Fix boundary violations
080eb82	Merge branch 'ticket/15820' into t/16453/cythonize_quiver_paths
7964292	Implement "gcd" for quiver paths

[simon-king-jena]

comment:9

The "largest overlap" was implemented in the latest commit of #15820. Here, I use it for "greatest common divisor" of paths P1, P2. This returns a triple C1, G, C2, so that G is of maximal length with the property P1=C1*G and P2=G*C2. Still needing review...

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

c827641

Provide Cython headers for quiver paths

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 7964292 to c827641

[simon-king-jena]

comment:11

In follow-up tickets, I will probably need to cimport quiver paths. Hence, I added a Cython header.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from c827641 to 7414f89

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

fd1675d	Merge branch 'develop' into t/15820/ticket/15820
93546db	Fix subsequence containment test.
4708952	Initial cythoned version of quiver paths
7a1f36e	Making cythoned quiver paths work
d083c55	Implement "gcd" for quiver paths
7414f89	Provide Cython headers for quiver paths

[simon-king-jena]

comment:13

In the outspoken expectation that nobody except myself has used the branch from this ticket, I took the liberty to rebase it on top of the latest fix at #15820. So, this is a forced push.

I suppose it still needs review.

[simon-king-jena]

Work Issues: merge new version of #15820

[simon-king-jena]

comment:16

Wow. This will be quite some work. By simply merging the new commits and doing the appropriate changes to cope with the changed API of "bounded integer sequences", I get some crashes and failures.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 7414f89 to 2d69388

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

3b2f713	Merge branch 'develop' into t/15820/ticket/15820
c69c67c	Use a bitmask when slicing bounded integer sequences
b331dc4	Fix mem leak converting zero-valued biseq_t to list
7b53dc8	Try to improve memory management for biseq_t, and add a stress test
7c9f0f2	Biseq refactored, so that only pointers are passed around.
0aa3cbc	Fix corner cases in item access for bounded integer sequences
f20dc09	Fix writing out of bounds, and assert that the bounds are respected
23000df	Merge branch 'u/SimonKing/ticket/15820' of git://trac.sagemath.org/sage into t/16453/cythonize_quiver_paths
2d69388	Cope with the recent API changes of #15820.

[simon-king-jena]

Changed work issues from merge new version of #15820 to none

[simon-king-jena]

comment:18

After all, it was easy to cope with the changes of #15820. All tests pass, needs review!!

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

e2f4a64

Count paths in quivers, in terms of generating functions

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 2d69388 to e2f4a64

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

d665747

Fix a typo in the doc

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from e2f4a64 to d665747

[simon-king-jena]

comment:21

I added a new feature: Counting of paths (in terms of generating functions), for arbitrary quivers. Needs review...

---

New commits:

d665747

Fix a typo in the doc

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from d665747 to 26f0029

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

26f0029

Fix further doc typos and the wording in a comment

[simon-king-jena]

comment:23

How can I obtain the letter é in Poincaré in the docs? I thought that \\'e would work---isn't latex used for typesetting? Apart from this minor detail, I think the code is fine.

---

New commits:

26f0029

Fix further doc typos and the wording in a comment

[nthiery]

comment:24

Replying to @simon-king-jena:

How can I obtain the letter é in Poincaré in the docs? I thought that \\'e would work---isn't latex used for typesetting?

Yes, but only for typesetting math stuff. I would just insert the character directly in unicode, and add the usual header to the file:

## -*- encoding: utf-8 -*-

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 26f0029 to f60c7c1

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

f60c7c1

Fix utf-8 characters

[simon-king-jena]

comment:26

Needs work. I just found the following totally wrong answer of poincare_series():

sage: S = DiGraph({0:{1:['a'], 2:['b']}, 1:{0:['c'], 1:['d']}, 2:{0:['e'],2:['f']}}).path_semigroup()
sage: S.inject_variables()
Defining e_0, e_1, e_2, a, b, c, d, e, f
sage: S.poincare_series((e*b, b*f, f*f, c*a, d*c, a*d, f*e, d*d*d*d, a*c*b*e, c*b*e*a*c, b*e*a*c*b))[0,0]
(948568795032094272909893509191171341133987714380927500611236528192824358010355712*t^6 - 474284397516047136454946754595585670566993857190463750305618264096412179005177856*t^5 + 1422853192548141409364840263786757011700981571571391250916854792289236537015533568*t^4 - 1422853192548141409364840263786757011700981571571391250916854792289236537015533568*t^3 + 1897137590064188545819787018382342682267975428761855001222473056385648716020711424*t^2 - 948568795032094272909893509191171341133987714380927500611236528192824358010355712*t + 474284397516047136454946754595585670566993857190463750305618264096412179005177856)/(-474284397516047136454946754595585670566993857190463750305618264096412179005177856*t^11 + 1422853192548141409364840263786757011700981571571391250916854792289236537015533568*t^10 - 1897137590064188545819787018382342682267975428761855001222473056385648716020711424*t^9 + 3319990782612329955184627282169099693968957000333246252139327848674885253036244992*t^8 - 2371421987580235682274733772977928352834969285952318751528091320482060895025889280*t^7 + 1897137590064188545819787018382342682267975428761855001222473056385648716020711424*t^6 + 2371421987580235682274733772977928352834969285952318751528091320482060895025889280*t^5 - 2371421987580235682274733772977928352834969285952318751528091320482060895025889280*t^4 + 1422853192548141409364840263786757011700981571571391250916854792289236537015533568*t^3 + 948568795032094272909893509191171341133987714380927500611236528192824358010355712*t^2 - 948568795032094272909893509191171341133987714380927500611236528192824358010355712*t + 474284397516047136454946754595585670566993857190463750305618264096412179005177856)

The correct answer would be a polynomil (what we have here is obtained from the principal 2-block of Mathieu group M11, which is finite). And the constant coefficient should just be 1 (since there is precisely one path of length zero from vertex 0 to vertex 0). I need to check the underlying maths, probably I got something wrong there.

[simon-king-jena]

comment:27

My counting formula is wrong, but in addition to that there seems to be a problem with quotient fields of rational polynomial rings. This shall be tracked in a different ticket, of course:

sage: P.<t> = QQ[]
sage: p = 4/(-4*t)
sage: p   # OK, fractions are not automatically reduced
4/(-4*t)
sage: p.reduce()
sage: p   # What the heck...
4/(-4*t)
sage: p == -1/t   # At least sage gets this right
True

[nthiery]

comment:28

Replying to @simon-king-jena:

My counting formula is wrong, but in addition to that there seems to be a problem with quotient fields of rational polynomial rings. This shall be tracked in a different ticket, of course:

sage: P.<t> = QQ[]
sage: p = 4/(-4*t)
sage: p   # OK, fractions are not automatically reduced
4/(-4*t)
sage: p.reduce()
sage: p   # What the heck...
4/(-4*t)
sage: p == -1/t   # At least sage gets this right
True

It's not completely unreasonable: in a field, the gcd of two elements can be arguably always set to 1. This is not what Sage does, but that's presumably Singular's choice.

    sage: gcd(4/1, 4/1)
    4

I don't know if it helps, but if you do the same calculation over ZZ, you get the desired result.

[simon-king-jena]

comment:29

Replying to @nthiery:

I don't know if it helps, but if you do the same calculation over ZZ, you get the desired result.

It helps to get a nicer normalisation. However, the main problem is that my formula is plain wrong.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

9a82bc3

Remove broken relative path counting

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from f60c7c1 to 9a82bc3

[simon-king-jena]

comment:31

I gave up path counting. Hence, I preserved the counting of all paths (which is correctly implemented), but I removed the function that was supposed to count those paths which do not contain a sub-path out of a finite list. It is broken, and I currently don't know how to fix it. So, better get the working bits into Sage ASAP. Needs review.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 9a82bc3 to a14a8af

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

cea38bb	Change doc according to the changed functionality of list_to_biseq
4611f8a	Minor changes in the docs
815d77c	mpn_r/lshift should only be used with strictly positive shift
6dfb1cb	Make contains_biseq interruptible and add to its doc
bfd7898	Merge branch 'develop' into t/15820/ticket/15820, since apparently the bitset code changed
47c639d	Rewrite bounded integer sequences using sage.misc.bitset
e3260e2	Typographical improvements
eeb30fb	Merge branch 't/15820/ticket/15820' into t/16453/cythonize_quiver_paths
aac3a04	Fix cornercase in unpickling
a14a8af	Merge branch 't/15820/ticket/15820' into t/16453/cythonize_quiver_paths, fixing pickling

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from a14a8af to 0670dd1

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

b182ba2	Use mpn_l/rshift only with nonzero shift
1f5a53e	Change the naming schemes of functions according to conventions in gmp and bitset
0670dd1	Merge branch 't/15820/ticket/15820' into t/16453/cythonize_quiver_paths

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 0670dd1 to 3c68256

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

ef69d1e	Create sage.data_structures, move biseq into it, and amend types in biseq
83be138	Reword documentation of biseq_s
3c68256	Merge branch 't/15820/ticket/15820' into t/16453/cythonize_quiver_paths (changed module location)