Opened 3 years ago

Closed 3 years ago

#26352 closed defect (fixed)

Lie algebra quotients are incorrect for some basis orders

Reported by: gh-ehaka Owned by:
Priority: major Milestone: sage-8.4
Component: algebra Keywords: Lie algebras, ideals, subalgebras, quotients
Cc: Merged in:
Authors: Eero Hakavuori Reviewers: Travis Scrimshaw
Report Upstream: N/A Work issues:
Branch: 25026d4 (Commits, GitHub, GitLab) Commit: 25026d48726e77d0f676351afcc3a6646ab90a8d
Dependencies: Stopgaps:

Status badges

Description

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.

Change History (9)

comment:1 Changed 3 years ago by gh-ehaka

  • Authors set to Eero Hakavuori
  • Branch set to u/gh-ehaka/subalgebra_basis_ordering-26352
  • Commit set to eec759470e1f089eb05b130790ce8e9864fd4304
  • Status changed from new to needs_review

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:

eec7594trac #26352: Lie subalgebra leading term ordering handling fix

comment:2 follow-up: Changed 3 years ago by tscrim

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`

comment:3 Changed 3 years ago by git

  • Commit changed from eec759470e1f089eb05b130790ce8e9864fd4304 to 1f58a6475f42f098cf33d9ed4ff939d5d54b4b88

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

1f58a64trac #26352: more efficient vector reordering

comment:4 in reply to: ↑ 2 ; follow-up: Changed 3 years ago by gh-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 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.

comment:5 in reply to: ↑ 4 ; follow-up: Changed 3 years ago by tscrim

  • Reviewers set to Travis Scrimshaw

Replying to gh-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.

comment:6 Changed 3 years ago by tscrim

  • Status changed from needs_review to positive_review

comment:7 Changed 3 years ago by git

  • Commit changed from 1f58a6475f42f098cf33d9ed4ff939d5d54b4b88 to 25026d48726e77d0f676351afcc3a6646ab90a8d
  • Status changed from positive_review to needs_review

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

25026d4trac #26352: removed orphaned import

comment:8 in reply to: ↑ 5 Changed 3 years ago by gh-ehaka

  • Status changed from needs_review to positive_review

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.

comment:9 Changed 3 years ago by vbraun

  • Branch changed from u/gh-ehaka/subalgebra_basis_ordering-26352 to 25026d48726e77d0f676351afcc3a6646ab90a8d
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.