Lie algebra quotients are incorrect for some basis orders

[ehaka]

The current implementation of Lie subalgebras confuses two things: the ordering of the basis of the ambient algebra and the ordering of the indices of the ambient algebra. If both orderings agree, then everything works fine:

sage: L.<a,b,c> = LieAlgebra(QQ, abelian=True)
sage: I = L.ideal([a+b,a+c])
sage: I.basis()
Family (a + b, a + c)
sage: Q = L.quotient(I)
sage: Q.basis()
Finite family {'a': a}

But if there is a mismatch in the ordering, then the output is wrong:

sage: L.<c,b,a> = LieAlgebra(QQ, abelian=True)
sage: I2 = L.ideal([a+b,a+c])
sage: I2.basis()
Family (-c + b, c + a)
sage: Q = L.quotient(I2)
sage: Q.basis()
Finite family {'b': b, 'a': a}

The difference is

sage: [I.lift(X).leading_support() for X in I.basis()]
['b', 'c']
sage: [I2.lift(X).leading_support() for X in I2.basis()]
['c', 'c']

That is, the behavior in the latter case is different to what is described in the doc. The indices which are not leading supports of I2 do not span a complementary subspace, but instead something bigger.

The issue is that currently the computation in basis takes its pivot elements based on the ordering of the ambient basis, whereas quotients and reduction assume they can work with leading_support, i.e. the ordering of the indices.

Component: algebra

Keywords: Lie algebras, ideals, subalgebras, quotients

Author: Eero Hakavuori

Branch/Commit: 25026d4

Reviewer: Travis Scrimshaw

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

[ehaka]

Branch: u/gh-ehaka/subalgebra_basis_ordering-26352

[ehaka]

comment:1

I changed the helper methods _to_m and _from_m to use the ordering of indices instead of the ordering of the basis. At the same time I added support for a custom ordering of indices with an additional order keyword to the subalgebra. The previously failing example now works as expected:

sage: L.<c,b,a> = LieAlgebra(QQ, abelian=True)
sage: I2 = L.ideal([a+b, a+c])
sage: I2.basis()
Family (b + a, c + a)
sage: Q = L.quotient(I2)
sage: Q.basis()
Finite family {'a': a}

The disadvantage is that the submodule computation is now more complicated as things needs to be sorted based on indices. Before the fix:

sage: L=LieAlgebra(QQ,3,step=5)
sage: L.dimension()
80
sage: I = L.ideal(L.basis().list()[0])
sage: time I.dimension()
CPU times: user 7.83 s, sys: 4.01 ms, total: 7.83 s
Wall time: 7.82 s
66

After the fix:

sage: time I.dimension()
CPU times: user 8.82 s, sys: 182 µs, total: 8.82 s
Wall time: 8.82 s
66

Having the extra functionality of custom orderings is nice, but it would be also good to have also a speed optimized one, where the submodule computation is done without worrying which elements are the pivot elements in the echelon form. In that case the reduction and complementary submodule computation would need special case handling though.

---

New commits:

eec7594

trac #26352: Lie subalgebra leading term ordering handling fix

[ehaka]

Commit: eec7594

[ehaka]

Author: Eero Hakavuori

[tscrim]

comment:2

Hmm...I see the problem:

sage: L.<a,b,c> = LieAlgebra(QQ, abelian=True)
sage: _.leading_support()
'c'
sage: L.<c,b,a> = LieAlgebra(QQ, abelian=True)
sage: sum(L.lie_algebra_generators()).leading_support()
'c'

When I designed this, I was thinking of doing linear algebra directly using the to_vector/from_vector methods because in those cases, it would be simply (un)wrapping. However, this could be seen as a bug as it does not respect the ordering of L.indices(). It might also be better overall to work with actual vector objects in general, but I am not sure off-hand.

I am not sure I like having the ideal handle an order argument, but it does mean we could have less ambient objects to worry about or create. It probably is the right thing to do overall.

I don't think this is efficient either:

return self.ambient().module().from_vector(vector(R, X_sorted))

I would avoid the call from_vector (which creates a dict and does the dumb, direct computation) and vector. I would just do

M = self.ambient().module()
B = M.basis()
return M.sum(R(mc[i]) * b[i] for i in self._reversed_indices if i in mc)

You don't even need to create the X_sorted.
Similar in _from_m.

I would @cached_method leading_monomials.

Little thing: trac #26352 -> :trac:`26352`

[sagetrac-git]

Changed commit from eec7594 to 1f58a64

[sagetrac-git]

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

1f58a64

trac #26352: more efficient vector reordering

[ehaka]

comment:4

Replying to @tscrim:

It might also be better overall to work with actual vector objects in general, but I am not sure off-hand.

I did not understand what you mean by this.

I am not sure I like having the ideal handle an order argument, but it does mean we could have less ambient objects to worry about or create. It probably is the right thing to do overall.

It is true that order is more of a property of the ambient Lie algebra than the ideals. At least that is how it is in the polynomial ring setting. I don't really have a use case where I would want to create ideals in several different orderings on the same Lie algebra, so it would be perfectly fine to move order to an optional parameter in LieAlgebra. Although if nothing else in the Lie algebra code uses the ordering then it might be a bit unclear what order actually effects. But maybe this would be an issue solved by its doc description?

I don't think this is efficient either:

return self.ambient().module().from_vector(vector(R, X_sorted))

I would avoid the call from_vector (which creates a dict and does the dumb, direct computation) and vector. I would just do

M = self.ambient().module()
B = M.basis()
return M.sum(R(mc[i]) * b[i] for i in self._reversed_indices if i in mc)

You don't even need to create the X_sorted.
Similar in _from_m.

Good call. It cut down the overhead in the previous testcase by a decent amount:

sage: L=LieAlgebra(QQ,3,step=5)
sage: I = L.ideal(L.basis().list()[0])
sage: time d=I.dimension()
CPU times: user 8.22 s, sys: 16.1 ms, total: 8.23 s
Wall time: 8.23 s

This is still a ~5% increase from prepatch, but not nearly as bad as the earlier 12-17% one.

I would @cached_method leading_monomials.

Little thing: trac #26352 -> :trac:`26352`

Added.

[tscrim]

comment:5

Replying to @ehaka:

Replying to @tscrim:

It might also be better overall to work with actual vector objects in general, but I am not sure off-hand.

I did not understand what you mean by this.

I had gotten an impression you were doing some work with the Lie algebra elements instead of their corresponding (typically underlying) vector. I guess you are not. Sorry for the noise.

I am not sure I like having the ideal handle an order argument, but it does mean we could have less ambient objects to worry about or create. It probably is the right thing to do overall.

It is true that order is more of a property of the ambient Lie algebra than the ideals. At least that is how it is in the polynomial ring setting. I don't really have a use case where I would want to create ideals in several different orderings on the same Lie algebra, so it would be perfectly fine to move order to an optional parameter in LieAlgebra. Although if nothing else in the Lie algebra code uses the ordering then it might be a bit unclear what order actually effects. But maybe this would be an issue solved by its doc description?

There is some reasons to have this. It might be faster in one order than other or you want different representatives. The catch with storing this with the ambient Lie algebra is that you have to create a new object for each order. Which is somewhat annoying at the very least. Unfortunately I don't think this is something simply solved by adding/changing stuff in the doc.

Anyways, this fixes a bug and I don't see any other obvious ways to speed this up right now. Positive review.

[tscrim]

Reviewer: Travis Scrimshaw

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. New commits:

25026d4

trac #26352: removed orphaned import

[sagetrac-git]

Changed commit from 1f58a64 to 25026d4

[ehaka]

comment:8

Replying to @tscrim:

There is some reasons to have this. It might be faster in one order than other or you want different representatives. The catch with storing this with the ambient Lie algebra is that you have to create a new object for each order. Which is somewhat annoying at the very least. Unfortunately I don't think this is something simply solved by adding/changing stuff in the doc.

I see your point, will let it be as is.

I removed the orphaned import of vector that patchbot found. Setting back to positive review as the code itself was not changed and tests still passed.

[vbraun]

Changed branch from u/gh-ehaka/subalgebra_basis_ordering-26352 to 25026d4