More competitive and comprehensive finite dimensional algebras #23707

simon-king-jena · 2017-08-25T07:48:37Z

Issues

Currently, sage.algebras.finite_dimensional_algebras.finite_dimensional_algebra_element is Python.
Multiplication is implemented by

self.__class__(self.parent(), self._vector * other._matrix)

which for some matrix implementations is not the fastest way:

sage: v = random_vector(GF(2),2000)
sage: M = random_matrix(GF(2),2000,2000)
sage: %timeit v*M
The slowest run took 8.27 times longer than the fastest. This could mean that an intermediate result is being cached.
100 loops, best of 3: 4.96 ms per loop
sage: %timeit M*v
1000 loops, best of 3: 172 µs per loop
sage: v = random_vector(GF(3),2000)
sage: M = random_matrix(GF(3),2000,2000)
sage: %timeit v*M
The slowest run took 37.59 times longer than the fastest. This could mean that an intermediate result is being cached.
1000 loops, best of 3: 1.11 ms per loop
sage: %timeit M*v
1000 loops, best of 3: 974 µs per loop
sage: v = random_vector(QQ,2000)
sage: M = random_matrix(QQ,2000,2000)
sage: %timeit v*M
1 loop, best of 3: 1.51 s per loop
sage: %timeit M*v
1 loop, best of 3: 3.32 s per loop
sage: v = random_vector(GF(9,'x'),2000)
sage: M = random_matrix(GF(9,'x'),2000,2000)
sage: %timeit v*M
1 loop, best of 3: 163 ms per loop
sage: %timeit M*v
1 loop, best of 3: 166 ms per loop

(Remark: The timings for GF(9,'x') are with MeatAxe)

vectormatrix respectively matrixvector may be a lot slower than matrix*matrix:

sage: M = random_matrix(GF(9,'x'),2000,2000)
sage: v = random_matrix(GF(9,'x'),2000,1)
sage: %timeit M*v
10 loops, best of 3: 52.4 ms per loop
sage: v1 = v.transpose()
sage: %timeit v1*M
The slowest run took 37.36 times longer than the fastest. This could mean that an intermediate result is being cached.
10000 loops, best of 3: 14.6 µs per loop

The last example is 163 ms vs. 14.6 µs!!!

In my applications, I need finite dimensional path algebra quotients. The current implementation corresponds to a finite dimensional path algebra quotient where the underlying quiver has a single vertex.
Creation of an element also involves construction of its multiplication matrix. From my experience, it can be faster (in some applications) to not construct the matrix of it right away, but be lazy. E.g., when one computes Gröbner bases, only multiplication by power products of the algebra generators are needed, and then it is faster to map the defining vector of the element repeatedly by multiplying with the matrices of the generators, instead of doing matrix by matrix multiplications.

Suggestion

Re-implement it in Cython
Replace vectormatrix by either rowmatrix or matrixcolumn, being flexible enough that both implementations are supported (because it depends on the field whether rowmatrix or matrix*column is fastest).
Allow using a quiver with more than one vertices.
Be more lazy, i.e. do costly computations such as the construction of the multiplication matrix only when needed.

CC: @tscrim @fchapoton @videlec

Component: algebra

Keywords: finite dimensional, algebra, quiver

Author: Simon King

Branch/Commit: 3cc3a27

Reviewer: Travis Scrimshaw

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

The text was updated successfully, but these errors were encountered:

jdemeyer · 2017-08-25T10:32:44Z

comment:2

FYI: PARI/GP has recently gained functionality to deal with general finite dimensional algebras. But it seems that this ticket is mostly about basic arithmetic, so I'm not sure that it's relevant.

simon-king-jena · 2017-08-25T10:37:48Z

comment:3

Replying to @jdemeyer:

FYI: PARI/GP has recently gained functionality to deal with general finite dimensional algebras. But it seems that this ticket is mostly about basic arithmetic, so I'm not sure that it's relevant.

This ticket is not necessarily about basic arithmetic. Eventually, I finally want to implement my F5 algorithm for modules over path algebra quotients (after being distracted by other things for several years), starting with finite dimensional quotients.

So, having an implementation of finite dimensional algebras over any field (but for me most importantly over finite not necessarily prime fields!) that is really competitive would be nice.

Can you give me a pointer for the PARI/GP implementation? Would it be difficult to wrap in cython?

jdemeyer · 2017-08-25T11:07:02Z

comment:4

Replying to @simon-king-jena:

So, having an implementation of finite dimensional algebras over any field (but for me most importantly over finite not necessarily prime fields!) that is really competitive would be nice.

An algebra over F_q is just a special case of an algebra over F_p. PARI/GP supports algebras over Q and over F_p.

Can you give me a pointer for the PARI/GP implementation?

See https://pari.math.u-bordeaux.fr/dochtml/html-stable/ section "Associative and central simple algebras".

Would it be difficult to wrap in cython?

I don't think so. Depending on your needs, you could also use cypari2.

simon-king-jena · 2017-08-25T11:11:47Z

comment:5

Replying to @jdemeyer:

Replying to @simon-king-jena:

So, having an implementation of finite dimensional algebras over any field (but for me most importantly over finite not necessarily prime fields!) that is really competitive would be nice.

An algebra over F_q is just a special case of an algebra over F_p.

I don't buy that. A matrix over F_p should be the same as an algebra over F_q, but the current default in sage differs totally in performance.

Anyway, if you wanted to say that PARI/GP is good in both cases then it's fine.

See https://pari.math.u-bordeaux.fr/dochtml/html-stable/ section "Associative and central simple algebras".

Thank you!

Would it be difficult to wrap in cython?

I don't think so. Depending on your needs, you could also use cypari2.

What's that?

jdemeyer · 2017-08-25T11:18:28Z

comment:6

cypari2 is a new package with what used to be sage.libs.pari. It is a Cython interface to PARI. It wraps PARI objects in Python objects. Using this is slower than directly calling the PARI library. On the other hand, if your computations spend most of the time in the PARI library, it wouldn't matter for performance.

simon-king-jena · 2017-08-25T11:20:05Z

comment:7

Replying to @jdemeyer:

cypari2 is a new package with what used to be sage.libs.pari. It is a Cython interface to PARI. It wraps PARI objects in Python objects. Using this is slower than directly calling the PARI library. On the other hand, if your computations spend most of the time in the PARI library, it wouldn't matter for performance.

Thanks. Are algebras wrapped? If found cypari2 by googling, but a quick look seems to indicate that the conversions are about numbers, not algebras.

simon-king-jena · 2017-08-25T11:29:18Z

comment:8

How can I do the following pari code in Sage?

  { m_i = [0,-1,0, 0;
           1, 0,0, 0;
           0, 0,0,-1;
           0, 0,1, 0];
    m_j = [0, 0,-1,0;
           0, 0, 0,1;
           1, 0, 0,0;
           0,-1, 0,0];
    m_k = [0, 0, 0, 0;
           0, 0,-1, 0;
           0, 1, 0, 0;
           1, 0, 0,-1];
    A = alginit(nfinit(y), [matid(4), m_i,m_j,m_k],  0); }

Defining the matrices works:

sage: Mi = pari("""
....: [0,-1,0, 0;
....:            1, 0,0, 0;
....:            0, 0,0,-1;
....:            0, 0,1, 0]""")
sage: Mj = pari("""
....: [0, 0,-1,0;
....:            0, 0, 0,1;
....:            1, 0, 0,0;
....:            0,-1, 0,0];""")
sage: Mk = pari("""
....: [0, 0, 0, 0;
....:            0, 0,-1, 0;
....:            0, 1, 0, 0;
....:            1, 0, 0,-1];""")
sage: Mj
[0, 0, -1, 0; 0, 0, 0, 1; 1, 0, 0, 0; 0, -1, 0, 0]
sage: Mi*Mk
[0, 0, 1, 0; 0, 0, 0, 0; -1, 0, 0, 1; 0, 1, 0, 0]

However, my attempts to define the algebra failed:

sage: pari("nfinit(y)").alginit([pari("matid(4)"), Mi,Mj,Mk], 0)
...
PariError: incorrect priority in nffactor: variable 0 >= y
sage: pari.alginit(pari("nfinit(y)"), [pari("matid(4)"), Mi,Mj,Mk], 0)
...
AttributeError: 'cypari2.pari_instance.Pari' object has no attribute 'alginit'

jdemeyer · 2017-08-25T11:31:49Z

comment:9

Replying to @simon-king-jena:

Are algebras wrapped?

Everything is wrapped. That's the nice thing about cypari2: it automagically wraps all GP functions (assuming that the argument types are understood; PARI functions taking functions as input are not supported for example).

It's probably not so relevant, but it's best to use #23518.

a quick look seems to indicate that the conversions are about numbers, not algebras.

Well yes, it's a Python package so it only supports a limited set of conversions for standard Python types. Sage does support more conversions though. In any case, don't be blinded by the conversions, that's really just a detail. If PARI supports your algorithms, surely the conversion between Sage and PARI should be possible to implement.

jdemeyer · 2017-08-25T11:44:16Z

comment:10

Use a different variable name :-)

sage: pari("nfinit(t)").alginit(["matid(4)", Mi, Mj, Mk], 0)

Note that you don't need pari() in the arguments of the method: the inputs are automatically converted to PARI. This means that strings are evaluated.

With #23518, you should be able to write this as

sage: pari.alginit("nfinit(t)", ["matid(4)", Mi, Mj, Mk], 0)

or

sage: pari.alginit(pari.nfinit("t"), [pari.matid(4), Mi, Mj, Mk], 0)

simon-king-jena · 2017-08-25T11:46:14Z

comment:11

Replying to @jdemeyer:

Use a different variable name :-)
sage: pari("nfinit(t)").alginit(["matid(4)", Mi, Mj, Mk], 0)

Why is that? pari("nfinit(y)") by itself does work.

simon-king-jena · 2017-08-25T11:54:38Z

comment:12

What's wrong with this?

sage: M1 = random_matrix(GF(2),1024,1024)
sage: M2 = random_matrix(GF(2),1024,1024)
sage: A = pari(GF(2)).alginit(["matid(1024)", M1, M2],0)
...
PariError: incorrect type in alginit (t_POL)

So, does the first argument of alginit really needs to be a number field, not a finite field?

simon-king-jena · 2017-08-25T12:03:25Z

comment:13

Reading that over finite fields one uses algtableinit, I tried

sage: MT = pari(["matid(1024)", M1,M2])
sage: A = MT.algtableinit(2)
...
PariError: incorrect type in algtableinit (t_VEC)

which didn't work either. Why?

simon-king-jena · 2017-08-25T12:06:25Z

comment:14

The following doesn't look promising:

sage: pM1 = pari(M1)
sage: pM2 = pari(M2)
sage: %timeit M1*M2
1000 loops, best of 3: 1.08 ms per loop
sage: %timeit pM1*pM2
1 loop, best of 3: 201 ms per loop

jdemeyer · 2017-08-25T13:55:21Z

comment:15

Replying to @simon-king-jena:

Reading that over finite fields one uses algtableinit, I tried
sage: MT = pari(["matid(1024)", M1,M2])
sage: A = MT.algtableinit(2)
...
PariError: incorrect type in algtableinit (t_VEC)
which didn't work either. Why?

Don't you need a list of 1024 matrices in dimension 1024?

simon-king-jena · 2017-08-25T15:12:23Z

comment:16

Replying to @jdemeyer:

Don't you need a list of 1024 matrices in dimension 1024?

Ouch, yes! Apparently I thought of constructing the algebra that is generated by these matrices (which I guess has dimension much larger than 1024).

simon-king-jena · 2017-08-25T15:32:59Z

comment:17

Replying to @jdemeyer:

Replying to @simon-king-jena:
Reading that over finite fields one uses algtableinit, I tried
sage: MT = pari(["matid(1024)", M1,M2])
sage: A = MT.algtableinit(2)
...
PariError: incorrect type in algtableinit (t_VEC)
which didn't work either. Why?
Don't you need a list of 1024 matrices in dimension 1024?

But in any case, Pari complains about type (t_VEC), not about value. So, the number of matrices isn't the only problem.

jdemeyer · 2017-08-25T15:39:46Z

comment:18

Replying to @simon-king-jena:

But in any case, Pari complains about type (t_VEC)

Don't take the PARI error messages too literally...

simon-king-jena · 2017-08-26T16:03:29Z

Branch: u/SimonKing/more_competitive_and_comprehensive_finite_dimensional_algebras

simon-king-jena · 2017-08-26T16:11:27Z

Commit: a34ee26

simon-king-jena · 2017-08-26T16:11:27Z

comment:20

I think I shouldn't be overambitious in this ticket: The finite-dimensional path algebra quotient stuff should be for a later ticket, where I will probably sub-class the now cythonised finite dimensional algebra elements.

Changes:

The element class is now in Cython.
The multiplication matrix of an element is now lazy, which means that initialisation of an element will be substantially faster.
An element is encoded by a matrix with a single row, not by a vector. As I have demonstrated, multiplying a single row matrix by a square matrix is always faster than multiplying a vector by a square matrix.

Caveat: It seems to me that OVER QQ multiplying a square matrix with a single-column matrix is faster than multiplying a single-row matrix with a square matrix. But that's the only case where I found that behaviour. Since I am not interested in the rational case anyway, I don't plan to provide a special implementation over QQ where elements are encoded as single-column matrices rather than single-row matrices.

PS: For me, tests pass...

New commits:

`a34ee26`	`Faster implementation of finite dimensional algebras`

simon-king-jena · 2017-08-26T16:41:49Z

comment:21

Back to pari:

sage: A = FiniteDimensionalAlgebra(GF(3), [Matrix([[1, 0], [0, 1]]), Matrix([[0, 1], [0, 0]])])
sage: pari([x.matrix() for x in A.gens()]).algtabaleinit()
Traceback (most recent call last):
...
PariError: incorrect type in algtableinit (t_VEC)

What's wrong?

simon-king-jena · 2017-08-26T19:43:01Z

comment:22

Replying to @simon-king-jena:

What's wrong?

I don't know why, but apparently Pari doesn't accept some associative algebras that are perfectly fine in Sage, while it accept others:

sage: B = FiniteDimensionalAlgebra(QQ, [Matrix([[1,0,0], [0,1,0], [0,0,1]]), Matrix([[0,0,0], [1,0,1], [0,0,0]]), Matrix([[0,0,0], [0,0,0], [1,0,1]])])
sage: pari([x.matrix() for x in B.gens()]).algtableinit()
[0, 0, 0, 0, 0, 0, [1, 0, 0; 0, 1, 0; 0, 0, 1], [1, 0, 0; 0, 1, 0; 0, 0, 1], [[1, 0, 0; 0, 1, 0; 0, 0, 1], [0, 0, 0; 1, 0, 1; 0, 0, 0], [0, 0, 0; 0, 0, 0; 1, 0, 1]], 0, [3, 0, 1]]
sage: A = FiniteDimensionalAlgebra(QQ, [Matrix([[1,0,0], [0,1,0], [0,0,0]]), Matrix([[0,1,0], [0,0,0], [0,0,0]]), Matrix([[0,0,0], [0,0,0], [0,0,1]])])
sage: pari([x.matrix() for x in A.gens()]).algtableinit()
---------------------------------------------------------------------------
PariError                                 Traceback (most recent call last)
<ipython-input-31-0e66e23e7476> in <module>()
----> 1 pari([x.matrix() for x in A.gens()]).algtableinit()

cypari2/auto_gen.pxi in cypari2.gen.Gen_auto.algtableinit()

cypari2/handle_error.pyx in cypari2.handle_error._pari_err_handle()

PariError: incorrect type in algtableinit (t_VEC)

Is there a clear reason or are associative algebras in Pari just broken?

simon-king-jena · 2017-08-27T11:13:40Z

comment:23

Strangely, the patchbot doesn't test it (although it needs review). I'm trying to ?kick it (I don't know if that's still needed nowadays, I learned about ?kick a couple of years ago).

fchapoton · 2017-08-27T11:24:41Z

comment:24

you need to fill the Author field, otherwise it is deemed unsafe

simon-king-jena · 2017-08-28T17:59:38Z

comment:70

Replying to @tscrim:

We definitely should override __getitem__ as that will be a lot faster than the generic implementation. However, there is a change in behavior:
sage: A.an_element()[5]
IndexError: matrix index out of range
Before this would return 0. It is arguable that it is the wrong behavior,

I do believe not raising an IndexError is wrong in that case.

However, the different behavior does make the iterator work, but that is a matter of a lack of implementation.

Here I am unsure what you are referring to by "different behaviour". As a matter of fact, iterator works now:

sage: A = FiniteDimensionalAlgebra(QQ, [Matrix([[1,0,0], [0,1,0], [0,0,0]]), Matrix([[0,1,0], [0,0,0], [0,0,0]]), Matrix([[0,0,0], [0,0,0], [0,0,1]])])
sage: x = A.1
sage: list(x)
[0, 1, 0]

I think it would be good to decide on and implement the behavior for __iter__ here:

1 - Iterate over the vector and yield the coefficients.
2 - Iterate over pairs (k, v), where k is the index/key and v is a non-zero coefficient.

My vote would be for 2 to be consistent with many (all?) the other algebras in Sage.

I don't think it is possible to be consistent, as even multi- and univariate polynomials aren't:

sage: R.<x,y> = QQ[]
sage: list(x^2+2*y)
[(1, x^2), (2, y)]
sage: R.<x> = QQ[]
sage: list(x^8)
[0, 0, 0, 0, 0, 0, 0, 0, 1]

Subsequently, your __len__ is a change in behavior, but it needs to be consistent with the __iter__. So we will need to choose.

A finite dimensional algebra is a finite dimensional vector space, and thus I believe one should be consistent with vectors, not with multivariate polynomials. And that is the case with the current implementation.

simon-king-jena · 2017-08-28T18:07:40Z

comment:71

Replying to @simon-king-jena:

Replying to @tscrim:

My vote would be for 2 to be consistent with many (all?) the other algebras in Sage.

I don't think it is possible to be consistent, as even multi- and univariate polynomials aren't:
sage: R.<x,y> = QQ[]
sage: list(x^2+2*y)
[(1, x^2), (2, y)]
sage: R.<x> = QQ[]
sage: list(x^8)
[0, 0, 0, 0, 0, 0, 0, 0, 1]

Also note that it is (v, k) not (k, v).

tscrim · 2017-08-28T19:29:37Z

comment:72

I wasn't thinking of polynomial rings (which are not [currently] in the category of ModulesWithBasis), but of subclasses of CombinatorialFreeModule:

sage: E = algebras.Exterior(QQ, 2)
sage: E.an_element()
2*e0 + 4*e1 + 1
sage: list(E.an_element())
[((), 1), ((1,), 4), ((0,), 2)]

sage: F = algebras.Free(QQ, 3, 'x')
sage: list(F.an_element())
[(x1, 3), (x0, 2), (1, 2)]
sage: F.an_element()
2 + 2*x0 + 3*x1

tscrim · 2017-08-28T19:44:26Z

comment:73

Replying to @simon-king-jena:

Replying to @tscrim:
We definitely should override __getitem__ as that will be a lot faster than the generic implementation. However, there is a change in behavior:
sage: A.an_element()[5]
IndexError: matrix index out of range
Before this would return 0. It is arguable that it is the wrong behavior,
I do believe not raising an IndexError is wrong in that case.

It probably is a side-effect of a generic implementation of _coefficient_fast, which is called from __getitem__, that doesn't do any safety checks (because it needs to support infinite bases). So, yes, I agree that raising an error is the right thing.

However, the different behavior does make the iterator work, but that is a matter of a lack of implementation.

Here I am unsure what you are referring to by "different behaviour". As a matter of fact, iterator works now:
sage: A = FiniteDimensionalAlgebra(QQ, [Matrix([[1,0,0], [0,1,0], [0,0,0]]), Matrix([[0,1,0], [0,0,0], [0,0,0]]), Matrix([[0,0,0], [0,0,0], [0,0,1]])])
sage: x = A.1
sage: list(x)
[0, 1, 0]

The old behavior for __getitem__ returned 0, where there seems to be a default __iter__ by Python that uses __getitem__ with ints until it raises an IndexError.

I think it would be good to decide on and implement the behavior for __iter__ here:

1 - Iterate over the vector and yield the coefficients.
2 - Iterate over pairs (k, v), where k is the index/key and v is a non-zero coefficient.

My vote would be for 2 to be consistent with many (all?) the other algebras in Sage.

I don't think it is possible to be consistent, as even multi- and univariate polynomials aren't:
sage: R.<x,y> = QQ[]
sage: list(x^2+2*y)
[(1, x^2), (2, y)]
sage: R.<x> = QQ[]
sage: list(x^8)
[0, 0, 0, 0, 0, 0, 0, 0, 1]

Good point. Always fun the differences between uni- and multivariate polynomials.

Subsequently, your __len__ is a change in behavior, but it needs to be consistent with the __iter__. So we will need to choose.

A finite dimensional algebra is a finite dimensional vector space, and thus I believe one should be consistent with vectors, not with multivariate polynomials. And that is the case with the current implementation.

See comment:72 for other algebras. Polynomials error out when trying to do, e.g., len(x^2+x) and sidestep the issue. It comes down to len meaning length as a column vector or length of the support.

I am okay with the current behavior, even if I would prefer it to agree with ModulesWithBasis objects/CombinatorialFreeModule subclasses, but I just wanted to bring up that it is a change. Since you prefer the current implementation and there is a green patchbot, I am setting a positive review.

simon-king-jena · 2017-08-28T19:52:21Z

comment:74

Thank you!

tscrim · 2017-08-28T20:20:45Z

comment:75

Thank you for your work on this. I look forward to having the quotients as well.

jdemeyer · 2017-08-28T21:11:20Z

comment:76

You are using cdef int in a few places where you might want cdef Py_ssize_t. Otherwise you are restricting to a size of 2³¹ for no good reason.

simon-king-jena · 2017-08-29T06:22:33Z

comment:77

Replying to @jdemeyer:

You are using cdef int in a few places where you might want cdef Py_ssize_t. Otherwise you are restricting to a size of 2³¹ for no good reason.

The restriction has already been there before:

sage: M = MatrixSpace(GF(2),1,2^32)()
sage: M[0,2^32-1]
---------------------------------------------------------------------------
OverflowError                             Traceback (most recent call last)
<ipython-input-2-0b1808df77ca> in <module>()
----> 1 M[Integer(0),Integer(2)**Integer(32)-Integer(1)]

/home/king/Sage/git/sage/src/sage/matrix/matrix0.pyx in sage.matrix.matrix0.Matrix.__getitem__ (build/cythonized/sage/matrix/matrix0.c:7018)()
    946                 if not PyIndex_Check(col_index):
    947                     raise TypeError("index must be an integer")
--> 948                 col = col_index
    949                 if col < 0:
    950                     col += ncols

OverflowError: value too large to convert to int

simon-king-jena · 2017-08-29T06:24:09Z

comment:78

Replying to @jdemeyer:

You are using cdef int in a few places where you might want cdef Py_ssize_t. Otherwise you are restricting to a size of 2³¹ for no good reason.

And doesn't Py_ssize_t denote some sort of signed integer? I guess I need an unsigned one. Py_size_t?

simon-king-jena · 2017-08-29T06:29:10Z

comment:79

One could even argue that using cdef int prevents one from crashing:

sage: M = MatrixSpace(GF(2),2^32)
sage: M(1)
------------------------------------------------------------------------
/home/king/Sage/git/sage/local/lib/python2.7/site-packages/cysignals/signals.so(+0x5e75)[0x7fb34704ee75]
/home/king/Sage/git/sage/local/lib/python2.7/site-packages/cysignals/signals.so(+0x5ec5)[0x7fb34704eec5]
/home/king/Sage/git/sage/local/lib/python2.7/site-packages/cysignals/signals.so(+0x8e97)[0x7fb347051e97]
/lib/x86_64-linux-gnu/libpthread.so.0(+0x11390)[0x7fb35378d390]
/home/king/Sage/git/sage/local/lib/python2.7/site-packages/sage/matrix/matrix_mod2_dense.so(+0xb102)[0x7fb1b8d71102]
/home/king/Sage/git/sage/local/lib/python2.7/site-packages/sage/matrix/matrix0.so(+0x407ee)[0x7fb1bc5a67ee]
/home/king/Sage/git/sage/local/lib/libpython2.7.so.1.0(PyEval_EvalFrameEx+0x48bd)[0x7fb353aa18ad]
/home/king/Sage/git/sage/local/lib/libpython2.7.so.1.0(PyEval_EvalCodeEx+0x81c)[0x7fb353aa688c]
/home/king/Sage/git/sage/local/lib/python2.7/site-packages/sage/misc/cachefunc.so(+0x16433)[0x7fb34572a433]
/home/king/Sage/git/sage/local/lib/python2.7/site-packages/sage/misc/cachefunc.so(+0x166c7)[0x7fb34572a6c7]
/home/king/Sage/git/sage/local/lib/python2.7/site-packages/sage/misc/cachefunc.so(+0x1698c)[0x7fb34572a98c]
/home/king/Sage/git/sage/local/lib/libpython2.7.so.1.0(PyObject_Call+0x43)[0x7fb3539ed483]
/home/king/Sage/git/sage/local/lib/libpython2.7.so.1.0(PyEval_EvalFrameEx+0x56da)[0x7fb353aa26ca]
/home/king/Sage/git/sage/local/lib/libpython2.7.so.1.0(PyEval_EvalCodeEx+0x81c)[0x7fb353aa688c]
/home/king/Sage/git/sage/local/lib/libpython2.7.so.1.0(PyEval_EvalFrameEx+0x8020)[0x7fb353aa5010]
/home/king/Sage/git/sage/local/lib/libpython2.7.so.1.0(PyEval_EvalCodeEx+0x81c)[0x7fb353aa688c]
/home/king/Sage/git/sage/local/lib/libpython2.7.so.1.0(+0x8567c)[0x7fb353a1e67c]
/home/king/Sage/git/sage/local/lib/libpython2.7.so.1.0(PyObject_Call+0x43)[0x7fb3539ed483]
/home/king/Sage/git/sage/local/lib/libpython2.7.so.1.0(+0x657ec)[0x7fb3539fe7ec]
/home/king/Sage/git/sage/local/lib/libpython2.7.so.1.0(PyObject_Call+0x43)[0x7fb3539ed483]
/home/king/Sage/git/sage/local/lib/libpython2.7.so.1.0(+0xc1985)[0x7fb353a5a985]
/home/king/Sage/git/sage/local/lib/libpython2.7.so.1.0(PyObject_Call+0x43)[0x7fb3539ed483]
/home/king/Sage/git/sage/local/lib/libpython2.7.so.1.0(PyEval_EvalFrameEx+0x56da)[0x7fb353aa26ca]
/home/king/Sage/git/sage/local/lib/libpython2.7.so.1.0(PyEval_EvalCodeEx+0x81c)[0x7fb353aa688c]
/home/king/Sage/git/sage/local/lib/libpython2.7.so.1.0(PyEval_EvalCode+0x19)[0x7fb353aa69a9]
/home/king/Sage/git/sage/local/lib/libpython2.7.so.1.0(PyEval_EvalFrameEx+0x7428)[0x7fb353aa4418]
/home/king/Sage/git/sage/local/lib/libpython2.7.so.1.0(PyEval_EvalCodeEx+0x81c)[0x7fb353aa688c]
/home/king/Sage/git/sage/local/lib/libpython2.7.so.1.0(PyEval_EvalFrameEx+0x8020)[0x7fb353aa5010]
/home/king/Sage/git/sage/local/lib/libpython2.7.so.1.0(PyEval_EvalCodeEx+0x81c)[0x7fb353aa688c]
/home/king/Sage/git/sage/local/lib/libpython2.7.so.1.0(PyEval_EvalFrameEx+0x8020)[0x7fb353aa5010]
/home/king/Sage/git/sage/local/lib/libpython2.7.so.1.0(PyEval_EvalCodeEx+0x81c)[0x7fb353aa688c]
/home/king/Sage/git/sage/local/lib/libpython2.7.so.1.0(PyEval_EvalFrameEx+0x8020)[0x7fb353aa5010]
/home/king/Sage/git/sage/local/lib/libpython2.7.so.1.0(PyEval_EvalCodeEx+0x81c)[0x7fb353aa688c]
/home/king/Sage/git/sage/local/lib/libpython2.7.so.1.0(PyEval_EvalFrameEx+0x8020)[0x7fb353aa5010]
/home/king/Sage/git/sage/local/lib/libpython2.7.so.1.0(PyEval_EvalCodeEx+0x81c)[0x7fb353aa688c]
/home/king/Sage/git/sage/local/lib/libpython2.7.so.1.0(PyEval_EvalFrameEx+0x8020)[0x7fb353aa5010]
/home/king/Sage/git/sage/local/lib/libpython2.7.so.1.0(PyEval_EvalCodeEx+0x81c)[0x7fb353aa688c]
/home/king/Sage/git/sage/local/lib/libpython2.7.so.1.0(PyEval_EvalFrameEx+0x8020)[0x7fb353aa5010]
/home/king/Sage/git/sage/local/lib/libpython2.7.so.1.0(PyEval_EvalCodeEx+0x81c)[0x7fb353aa688c]
/home/king/Sage/git/sage/local/lib/libpython2.7.so.1.0(PyEval_EvalCode+0x19)[0x7fb353aa69a9]
/home/king/Sage/git/sage/local/lib/libpython2.7.so.1.0(PyRun_FileExFlags+0x8a)[0x7fb353acaa4a]
/home/king/Sage/git/sage/local/lib/libpython2.7.so.1.0(PyRun_SimpleFileExFlags+0xd7)[0x7fb353acbdf7]
/home/king/Sage/git/sage/local/lib/libpython2.7.so.1.0(Py_Main+0xc3e)[0x7fb353ae24be]
/lib/x86_64-linux-gnu/libc.so.6(__libc_start_main+0xf0)[0x7fb352cc2830]
python(_start+0x29)[0x400719]
------------------------------------------------------------------------
Attaching gdb to process id 6413.

Failed to run gdb.
Failed to run gdb.
Install gdb for enhanced tracebacks.
------------------------------------------------------------------------
Unhandled SIGSEGV: A segmentation fault occurred.
This probably occurred because a *compiled* module has a bug
in it and is not properly wrapped with sig_on(), sig_off().
Python will now terminate.
------------------------------------------------------------------------
Segmentation fault (core dumped)

jdemeyer · 2017-08-29T08:31:49Z

comment:80

Replying to @simon-king-jena:

The restriction has already been there before:

The fact that a certain bug exists already is not a good reason to add more bugs of a similar nature.

jdemeyer · 2017-08-29T08:34:01Z

comment:81

Replying to @simon-king-jena:

And doesn't Py_ssize_t denote some sort of signed integer?

Yes, it does. However, Python generally uses Py_ssize_t for sizes (say, of lists or tuples). Also, in Sage, the number of rows/columns of a matrix is already stored as Py_ssize_t:

cdef class Matrix(ModuleElement):
    # All matrix classes must be written in Cython
    cdef Py_ssize_t _nrows
    cdef Py_ssize_t _ncols

sagetrac-git · 2017-08-29T09:01:30Z

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

`3cc3a27`	`Use Py_ssize_t to iterate over matrix indices`

sagetrac-git · 2017-08-29T09:01:30Z

Changed commit from 2fd7595 to 3cc3a27

simon-king-jena · 2017-08-29T09:02:29Z

comment:83

Replying to @jdemeyer:
Also, in Sage, the number of rows/columns of a matrix is already stored as Py_ssize_t:

cdef class Matrix(ModuleElement):
    # All matrix classes must be written in Cython
    cdef Py_ssize_t _nrows
    cdef Py_ssize_t _ncols

OK, that's a good reason. I changed to Py_ssize_t.

tscrim · 2017-09-17T14:55:47Z

comment:84

Jeroen, any more comments (or things not addressed)?

jdemeyer · 2017-09-18T07:46:24Z

comment:85

Not really. Anyway, I have not looked deeply into this ticket, I was just pointing a few random things.

tscrim · 2017-10-26T00:15:09Z

comment:86

I let this drop off. Whoops. Back to positive review.

vbraun · 2017-10-29T10:32:06Z

Changed branch from u/SimonKing/more_competitive_and_comprehensive_finite_dimensional_algebras to 3cc3a27

simon-king-jena added this to the sage-8.1 milestone Aug 25, 2017

simon-king-jena added c: algebra labels Aug 25, 2017

This comment has been minimized.

Sign in to view

simon-king-jena added the s: needs review label Aug 26, 2017

tscrim added s: positive review and removed s: needs review labels Aug 28, 2017

jdemeyer added s: needs work and removed s: positive review labels Aug 28, 2017

simon-king-jena added s: needs review and removed s: needs work labels Aug 29, 2017

tscrim added s: positive review and removed s: needs review labels Oct 26, 2017

vbraun removed the s: positive review label Oct 29, 2017

vbraun closed this as completed in 14d3ce4 Oct 29, 2017

simon-king-jena mentioned this issue Dec 29, 2022

Pickling be construction for element classes #23749

Open

More competitive and comprehensive finite dimensional algebras #23707

More competitive and comprehensive finite dimensional algebras #23707

Comments

simon-king-jena commented Aug 25, 2017

This comment has been minimized.

jdemeyer commented Aug 25, 2017

simon-king-jena commented Aug 25, 2017

jdemeyer commented Aug 25, 2017

simon-king-jena commented Aug 25, 2017

jdemeyer commented Aug 25, 2017

simon-king-jena commented Aug 25, 2017

simon-king-jena commented Aug 25, 2017

jdemeyer commented Aug 25, 2017

jdemeyer commented Aug 25, 2017

simon-king-jena commented Aug 25, 2017

simon-king-jena commented Aug 25, 2017

simon-king-jena commented Aug 25, 2017

simon-king-jena commented Aug 25, 2017

jdemeyer commented Aug 25, 2017

simon-king-jena commented Aug 25, 2017

simon-king-jena commented Aug 25, 2017

jdemeyer commented Aug 25, 2017

simon-king-jena commented Aug 26, 2017

simon-king-jena commented Aug 26, 2017

simon-king-jena commented Aug 26, 2017

simon-king-jena commented Aug 26, 2017

simon-king-jena commented Aug 26, 2017

simon-king-jena commented Aug 27, 2017

fchapoton commented Aug 27, 2017

simon-king-jena commented Aug 28, 2017

simon-king-jena commented Aug 28, 2017

tscrim commented Aug 28, 2017

tscrim commented Aug 28, 2017

simon-king-jena commented Aug 28, 2017

tscrim commented Aug 28, 2017

jdemeyer commented Aug 28, 2017

simon-king-jena commented Aug 29, 2017

simon-king-jena commented Aug 29, 2017

simon-king-jena commented Aug 29, 2017

jdemeyer commented Aug 29, 2017

jdemeyer commented Aug 29, 2017

sagetrac-git mannequin commented Aug 29, 2017

sagetrac-git mannequin commented Aug 29, 2017

simon-king-jena commented Aug 29, 2017

tscrim commented Sep 17, 2017

jdemeyer commented Sep 18, 2017

tscrim commented Oct 26, 2017

vbraun commented Oct 29, 2017