Cythonise path algebra elements

[simon-king-jena]

16453 provides a Cython version of quiver paths. The purpose of this ticket is to introduce a Cython implementation of path algebra elements.

Note that the arithmetic appears to be faster than the current default implementation of free associative algebras. So, it might make sense to use (the more general) path algebras to become the default for free associative algebras.

The next step shall be to implement computation of Gröbner bases. minimal generating sets and minimal projective resolutions for modules over path algebras, with a non-commutative F5 algorithm.

Depends on #16453 Depends on #17526

CC: @nthiery @nathanncohen @egunawan

Component: algebra

Keywords: path algebra elements, days64.5, days65

Author: Simon King

Branch/Commit: 5b4ed6e

Reviewer: Frédéric Chapoton

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

[simon-king-jena]

Changed keywords from none to path algebra elements

[simon-king-jena]

Description changed:

--- 
+++ 
@@ -1 +1,5 @@
+#16453 provides a Cython version of quiver paths. The purpose of this ticket is to introduce a Cython implementation of path algebra elements.

+Note that the arithmetic appears to be faster than the current default implementation of free associative algebras. So, it might make sense to use (the more general) path algebras to become the default for free associative algebras.
+
+The next step shall be to implement computation of Gröbner bases. minimal generating sets and minimal projective resolutions for modules over path algebras, with a non-commutative F5 algorithm.

[simon-king-jena]

Author: Simon King

[simon-king-jena]

Dependencies: #16453

[simon-king-jena]

Branch: u/SimonKing/cythonise_path_algebra_elements

[simon-king-jena]

Commit: 431b7f9

[simon-king-jena]

Last 10 new commits:

c48b312	Cythoned path algebra elements
e85f3aa	Implement mul, cmp, hash; fix add
61c283a	Faster hash; fixed multiplication; temporary: sanity checks
1fda709	Path algebra elements now feature complete; minor changes to path algebras
15ed81d	Use PathAlgebraElement for path algebras. Still missing: Pickling
2b16f3a	Pickling of path algebra elements
6daa985	Fix conversion of path algebra elements
269a607	Verify during printing of a polynomial that the terms are ordered. Only allow degree orders. More docs.
b32b034	Conversion dict->path algebra element. Full doctest coverage.
431b7f9	Merge branch 't/17435/cythonise_path_algebra_elements' into cythonize_path_algebra_element

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

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

99da336

Fixing some typos in the docs

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

Changed commit from 431b7f9 to 99da336

[simon-king-jena]

comment:6

I just noticed a problem, most likely in _sub_:

sage: P = DiGraph({1:{1:['x','y','z']}}).path_semigroup().algebra(GF(25,'t'))
sage: P.inject_variables()
Defining e_1, x, y, z
sage: e_1 + 2*x*y*x*z*z*z*x*y - z*z*x*y*z*z*x*y   # gives wrong result
e_1 + 3*x*y*x*z*z*z*x*y + 4*z*z*x*y*z*z*x*y
sage: e_1 - z*z*x*y*z*z*x*y + 2*x*y*x*z*z*z*x*y   # gives correct result
e_1 + 2*x*y*x*z*z*z*x*y + 4*z*z*x*y*z*z*x*y

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

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

27b6ea9

Fix subtraction of path algebra elements

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

Changed commit from 99da336 to 27b6ea9

[simon-king-jena]

comment:9

Fixed. The problem was that under certain circumstances, the computation c = a - b has put the negative of a term of a into c, where it should have put a copy of the term.

Now the tests work. I also included a comparison with the letterplace implementation of free associative algebras. Letterplace is faster, but it is restricted to homogeneous elements.

[simon-king-jena]

comment:10

PS: I wonder whether I should implement Karatsuba multiplication...

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

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

fab190e	Kill list for path algebra elements
6f07e26	Avoid needless term comparisons during multiplication

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

Changed commit from 27b6ea9 to 6f07e26

[simon-king-jena]

comment:12

I did two changes:

• I implemented a kill list for terms. It has not as much impact as I originally thought, so, maybe it makes sense to revert that change. However, when I did some c-profiling, a small improvement was visible.
• In the multiplication of path algebra elements, I did far more term comparisons than needed. Actually (again by c-profiling) I found that half of the time was spent on the comparisons. In the latest commit, I avoid some comparisons by book keeping.

Now, at least according to few benchmarks, the arithmetic for path algebra elements is faster than the arithmetic for both available implementations of free associative algebra elements (one of them, letterplace, is available for homogeneous elements only). Hence, in the long run, it might be worth while to implement free associative algebras as quiver algebras!

At least with git-rerere enabled, the dependency merges cleanly into the branch. So, no merge commit this time...

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

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

a961dfd

Remove c-profiling

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

Changed commit from 6f07e26 to a961dfd

[simon-king-jena]

comment:14

I forgot to remove some lines that enabled c-profiling (which was useful to get my implementation to better speed). Without it, it becomes a bit faster.

[simon-king-jena]

comment:15

Replying to @simon-king-jena:

I forgot to remove some lines that enabled c-profiling (which was useful to get my implementation to better speed). Without it, it becomes a bit faster.

... and thus I also updated the timings appearing in the docs.

[simon-king-jena]

comment:16

I just noticed that the letterplace implementation leaks in the following example:

sage: L.<x,y,z> = FreeAlgebra(GF(25,'t'), implementation='letterplace')
sage: p = x^4+x*y*x*z+2*z^2*x*y
sage: while 1:
....:     print get_memory_usage()
....:     z = p^7

The corresponding example with path algebras does not leak (one only sees that the kill list fills up in the first few iterations):

sage: P = DiGraph({1:{1:['x','y','z']}}).path_semigroup().algebra(GF(25,'t'))
sage: p = sage_eval('x+y*z*x+2*y-z+1', P.gens_dict())
sage: while 1:
....:     print get_memory_usage()
....:     z = p^7

That might explain why letterplace is slower than path algebras. In any case, fixing the leak should be the purpose of another ticket.

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

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

880801f	Make doctests of path algebra elements work on 64 bit
3c8ae84	Fix deallocation of kill list

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

Changed commit from a961dfd to 3c8ae84

[simon-king-jena]

comment:18

I have changed my operating system from openSUSE 12.3 32bit to openSUSE 13.2 64bit. Doing so, I found that one doctest depended on the bits. So, I fixed that.

Also, I found one crash, and it is astounding that it did not occur before: When I put a term on the kill list, I dereference the coefficient. When I remove the kill list (which happens when Sage quits) then I dereferenced the coefficient again. That's of course wrong, and corrected in the second commit.

Something else: While the change from 32bit to 64bit did not make letterplace faster, the timings for my implementation improved by as much as 20%! So, I am looking forward to my applications :-).

Concerning timings: Is it ok to include timings into the docs? After all, they are on a particular machine etc. Is there a policy? If so, I could remove the corresponding parts from sage.quivers.algebra_elements.

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

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

b080629

Elaborate on the role of different implementations of free algebras

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

Changed commit from 3c8ae84 to b080629

[simon-king-jena]

comment:20

According to Nathann's comment on sage-devel, including timings is ok, as long as the timings are consistent on different machines.

In this case, on openSUSE 32bit, arithmetic for path algebra elements is faster than arithmetic for letterplace free algebra elements, which is much faster than arithmetic for the default implementation of free algebra elements. On openSUSE 64bit, it is the same ranking; while letterplace is not faster in 64bit than in 32bit, the path algebra implementation becomes 20% faster in this example.

Of course, the purpose of the three implementations is different:

The letterplace implementation only allows to deal with homogeneous elements, but in contrast to the default implementation for free algebras it comes with standard basis computations, allowing to construct graded algebra quotients.

Path algebras are more general then free associative algebras, and homogeneity is not required. At the moment, standard bases are not available---but in fact this should be the next step. I plan to finish implementing a non-commutitive F5 algorithm, which can compute standard bases for one and two-sided ideals of modules over path algebra quotients (in particular, of ideals in path algebras, so that one can deal with algebra quotients), provided of course that the computation terminates in finite time. And moreover, it will be able to compute minimal generating sets of modules over basic algebras.

So, in the long run, it might make sense to replace the current default implementation of free algebra elements, modelling free associative algebras as a special case of path algebras. But that's for future. I hope that for now the comment on the relation of the three implementations is fine.

[simon-king-jena]

comment:21

Sigh. Develop doesn't merge cleanly. So, merge is needed. Moreover, it would be good to make #17526 a dependency, since that fixes a bug for bitsets that is relevant here.

[simon-king-jena]

Work Issues: Merge

[simon-king-jena]

Changed dependencies from #16453 to #16453 #17526

[simon-king-jena]

comment:22

Arrgh. I hate git's merge. And I hate the fact that I had to re-install git-rerere on my laptop, since I had to re-install my OS.

[simon-king-jena]

comment:23

Replying to @simon-king-jena:

And I hate the fact that I had to re-install git-rerere on my laptop, since I had to re-install my OS.

Or not? Apparently git rerere is there. Nevertheless, I am asked to do merges that I have been done in the past (repeatedly).

[simon-king-jena]

comment:24

What the heck is wrong with git?

I just tried to merge #17526 with the branch here. #17526 only changes bitset.pxi. But git merge asks me to resolve conflicts in bounded_integer_sequences.pyx. I am tired of these artificial conflicts that git is producing.

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

Changed commit from b080629 to cd77a17

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

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

cd77a17

Merge branch 't/15820/ticket/15820' into t/17435/cythonise_path_algebra_elements

[simon-king-jena]

comment:26

Argh. The merge has failed.

[simon-king-jena]

comment:27

Replying to @simon-king-jena:

Argh. The merge has failed.

In fact, git merge has reverted changes from #16453. Frankly, at the moment my impression is that git is very bad for productivity.

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

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

7564770	Merge branch 'develop' into t/15820/ticket/15820
962c674	Merge branch 'u/jdemeyer/ticket/15820' of git://trac.sagemath.org/sage into t/15820/ticket/15820
63d2693	More descriptive function name for bounded integer sequences
af690ca	Merge branch 't/15820/ticket/15820' into t/16453/cythonize_quiver_paths
126ee26	Merge branch 't/15820/ticket/15820' into t/16453/cythonize_quiver_paths
6a6d913	Do less imports in path's pxd file; signal handling in one function
73b6539	revert a change to pickling of bounded integer sequences
73ac689	Allow to choose two alternative encodings of paths
0432297	Remove alternative implementation of paths, because of benchmark results
7d9d492	Merge branch 't/16453/cythonize_quiver_paths' into t/17435/cythonise_path_algebra_elements

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

Changed commit from cd77a17 to 7d9d492

[simon-king-jena]

comment:29

As it turns out, the "32bit vs 64bit" problem should be fixed at #16453, not here. With mercurial, one could just move the patch from here to there. With git, I expect it will be a lot more difficult to cope with an erroneous commit. If I understood Volker's advice, I should not try to merge #16453 again (after fixing the error there, we will have a new merge conflict) as long as the branch here works. So, I just leave it.

[simon-king-jena]

comment:30

It could be that I will rewrite everything from scratch. Reason: Volker gave some good arguments on sage-devel why I should not use C structs for the terms on PyObject* for the coefficients (even though it seems I got the reference counting right...), but should rely on Python objects. It could be that I'll end up implementing an element of a path algebra as a typed memoryview...

We will see.

[simon-king-jena]

Changed branch from u/SimonKing/cythonise_path_algebra_elements to public/17435/cythonise_path_algebra_elements

[simon-king-jena]

Changed commit from 7d9d492 to ba2ed8d

[simon-king-jena]

comment:32

Since supposedly nobody but me was using the old branch of this ticket, since nobody was attempting a full review, since the branch of one dependency has changed and since the commit history was a bit messy, I created a new branch by rebasing and attached it here.

The resulting code did not change. I still use linked lists. Actually I am not convinced that arrays could be better, since my impression is that arithmetic operations would involve copying the content of the arrays around, whereas with linked lists one has just to redirect pointers.

Anyway, I plan to do some tests with arrays, but I think the code is ready for review, and a change to arrays could be done on a different ticket, if useful.

---

New commits:

f2a69ab	More useful functions for biseq_t
fd3fd82	Better hash function for biseq_t. Document the new functions.
b10c172	Cython implementation of quiver paths
9d56888	Use Cython implementation of paths in path algebras/representations
3b26941	Cythoned path algebra elements
6118f0a	Kill list for path algebra elements
0433d0c	Avoid needless term comparisons during multiplication
ba2ed8d	Elaborate on the role of different implementations of free algebras

[simon-king-jena]

comment:33

The branch does not cleanly merge into develop. Hence, I have to resolve a conflict and push here.

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

Changed commit from ba2ed8d to 5a5e35d

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

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

0a72b46	Add a doctest for _nb_arrows
70503e3	Clarify the documentation of _cmp_c_impl
8984ea7	Merge branch 'public/ticket/16453' of git://trac.sagemath.org/sage into t/17435/cythonise_path_algebra_elements_6.7.beta
5a5e35d	Merge branch 'public/17435/cythonise_path_algebra_elements' of git://trac.sagemath.org/sage into t/17435/cythonise_path_algebra_elements_6.7.beta

[simon-king-jena]

Changed work issues from Merge to Fix segfaults

[simon-king-jena]

comment:35

The merge conflict is resolved. However, it is not ready for review yet: There are segfaults related with coercion. That's bad.