Opened 4 years ago

Closed 4 years ago

#26076 closed enhancement (fixed)

Free nilpotent Lie algebras

Reported by: gh-ehaka Owned by:
Priority: major Milestone: sage-8.4
Component: algebra Keywords: Lie algebras, nilpotent
Cc: tscrim Merged in:
Authors: Eero Hakavuori Reviewers: Travis Scrimshaw
Report Upstream: N/A Work issues:
Branch: 664fbec (Commits, GitHub, GitLab) Commit: 664fbeceb2594310cb95ffe1df434e41ceb5ebbd
Dependencies: #26074 Stopgaps:

Status badges

Description

Implement the construction of free nilpotent Lie algebras, i.e. Lie algebras where the only additional relations among the brackets are that iterated brackets longer than the nilpotency step must vanish.

Change History (12)

comment:1 Changed 4 years ago by gh-ehaka

Some implementation already exists in an external private codebase that I need to clean up and import into Sage.

comment:2 Changed 4 years ago by gh-ehaka

  • Authors set to Eero Hakavuori
  • Branch set to u/gh-ehaka/free_nilpotent_lie_algebras-26076
  • Commit set to cb8a1030ea0da83777e06bbf8aea9876819b2567
  • Status changed from new to needs_review

The adapted version of the free nilpotent Lie algebra construction is in the commits. I removed the parameter free from the method sage.algebras.lie_algebras.nilpotent_lie_algebra.NilpotentLieAlgebra of #26074, as the parameter seemed to be redundant.


New commits:

19c27ebNew subcategories of Lie algebras (nilpotent, graded, stratified) and a base class for nilpotent Lie algebras
f58cdddImplementation of the construction of free nilpotent Lie algebras
cb8a103Changed doctests to use free nilpotent Lie algebras as more natural examples of graded or stratified Lie algebras

comment:3 Changed 4 years ago by git

  • Commit changed from cb8a1030ea0da83777e06bbf8aea9876819b2567 to 31fa53ab88a2d593f4fa2992f04d12e6f71f9930

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

158bfdbFix to product_space() for when L is not a true subalgebra of A.
293901eFixed a test for _test_generated_by_degree_one().
8658e9dFixing print order for fin-dim nilpotent Lie algebras with basis.
726639fSome last little cleanup.
8b3c585A better failure example for _test_generated_by_degree_one and some more doc.
a1e1aceRefactored nilpotent Lie algebra constructor into Lie algebra constructor
14fcd30Deduction rule for the fact that finite dimensional stratified Lie algebras are nilpotent
f1a0b1eDocstring fix for indexing of grading of a stratification
4d4bdf6Merge remote-tracking branch 'trac/public/lie_algebras/base_class_nilponent-26074' into free_nilpotent_lie_algebras
31fa53aAdded free nilpotent Lie algebras to LieAlgebra constructor

comment:4 Changed 4 years ago by git

  • Commit changed from 31fa53ab88a2d593f4fa2992f04d12e6f71f9930 to b7c8a2a95b985b716a440bbdc89342528b5817ba

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

a3dccfdMerge branch 'public/lie_algebras/base_class_nilponent-26074' of git://trac.sagemath.org/sage into public/lie_algebras/base_class_nilponent-26074
0fa41adFixing doctests, making category an arugment, and other small tweaks.
53a10beAdding an extra doctest and fix for the category option.
d7077cdMerge remote-tracking branch 'trac/public/lie_algebras/base_class_nilponent-26074' into u/gh-ehaka/free_nilpotent_lie_algebras-26076
b7c8a2aFixed category parameter of initialization of free nilpotent Lie algebra

comment:5 Changed 4 years ago by git

  • Commit changed from b7c8a2a95b985b716a440bbdc89342528b5817ba to 09b54f536e775b1f7c6b267ac25a77fbbdd52c99

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

a5ec3adMoving the axioms around for better printing.
09b54f5Merge remote-tracking branch 'trac/public/lie_algebras/base_class_nilponent-26074' into u/gh-ehaka/free_nilpotent_lie_algebras-26076

comment:6 Changed 4 years ago by git

  • Commit changed from 09b54f536e775b1f7c6b267ac25a77fbbdd52c99 to b70bebd70696d8d22a58b422f90c701cb459f2db

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

b70bebddoctest fix for changed category printing

comment:7 Changed 4 years ago by tscrim

  • Branch changed from u/gh-ehaka/free_nilpotent_lie_algebras-26076 to public/lie_algebras/free_nilpotent-26076
  • Commit changed from b70bebd70696d8d22a58b422f90c701cb459f2db to a60ef683b3747b7d129b14b6834d0f329820a4fa
  • Reviewers set to Travis Scrimshaw

I have made some documentation tweaks and a little better normalization and testing of the input. I have also obtained a speedup of the creation of the free nilpotent lie algebra (although it costs a big more in terms of memory usage by having to hold 2 copies of all of the Lyndon word tuples in memory):

%sage: %time L = LieAlgebra(QQ, 3, step=3)
CPU times: user 48 ms, sys: 4 ms, total: 52 ms
Wall time: 50.3 ms
sage: %time L = LieAlgebra(QQ, 5, step=3)
CPU times: user 16 ms, sys: 0 ns, total: 16 ms
Wall time: 12.7 ms
sage: %time L = LieAlgebra(QQ, 5, step=4)
CPU times: user 92 ms, sys: 0 ns, total: 92 ms
Wall time: 88.3 ms
sage: %time L = LieAlgebra(QQ, 5, step=5)
CPU times: user 1.45 s, sys: 28 ms, total: 1.48 s
Wall time: 1.47 s
sage: %time L = LieAlgebra(QQ, 6, step=3)
CPU times: user 16 ms, sys: 8 ms, total: 24 ms
Wall time: 21 ms
sage: %time L = LieAlgebra(QQ, 6, step=4)
CPU times: user 368 ms, sys: 36 ms, total: 404 ms
Wall time: 356 ms
sage: %time L = LieAlgebra(QQ, 6, step=5)
CPU times: user 8.83 s, sys: 148 ms, total: 8.98 s
Wall time: 8.97 s

vs prev

sage: %time L = LieAlgebra(QQ, 3, step=3)
CPU times: user 44 ms, sys: 8 ms, total: 52 ms
Wall time: 49.3 ms
sage: %time L = LieAlgebra(QQ, 5, step=3)
CPU times: user 12 ms, sys: 4 ms, total: 16 ms
Wall time: 15.5 ms
sage: %time L = LieAlgebra(QQ, 5, step=4)
CPU times: user 144 ms, sys: 12 ms, total: 156 ms
Wall time: 142 ms
sage: %time L = LieAlgebra(QQ, 5, step=5)
CPU times: user 2.29 s, sys: 24 ms, total: 2.32 s
Wall time: 2.31 s
sage: %time L = LieAlgebra(QQ, 6, step=3)
CPU times: user 24 ms, sys: 0 ns, total: 24 ms
Wall time: 25.2 ms
sage: %time L = LieAlgebra(QQ, 6, step=4)
CPU times: user 536 ms, sys: 28 ms, total: 564 ms
Wall time: 533 ms
sage: %time L = LieAlgebra(QQ, 6, step=5)
CPU times: user 13.7 s, sys: 204 ms, total: 13.9 s
Wall time: 13.9 s

If my changes are good, then positive review.


New commits:

8f7aac5Added missing files to documentation, removed non-existent one that was causing docbuild to fail
120c02aSome trivial fixes.
7699db4Merge branch 'u/gh-ehaka/free_nilpotent_lie_algebras-26076' of git://trac.sagemath.org/sage into public/lie_algebras/free_nilpotent-26076
d1fe093Some reviewer changes and tweaks.
a60ef68Speedup constructor for free Nilpotent Lie algebras.

comment:8 Changed 4 years ago by tscrim

  • Cc tscrim added

comment:9 Changed 4 years ago by git

  • Commit changed from a60ef683b3747b7d129b14b6834d0f329820a4fa to 664fbeceb2594310cb95ffe1df434e41ceb5ebbd

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

664fbecChanging r=10 as cutoff to requiring a linear ordering.

comment:10 follow-up: Changed 4 years ago by tscrim

I also changed the r = 10 case to not be accepted for the index naming because you are using 1-based indices.

comment:11 in reply to: ↑ 10 Changed 4 years ago by gh-ehaka

  • Status changed from needs_review to positive_review

Replying to tscrim:

I have made some documentation tweaks and a little better normalization and testing of the input.

All good changes.

I have also obtained a speedup of the creation of the free nilpotent lie algebra (although it costs a big more in terms of memory usage by having to hold 2 copies of all of the Lyndon word tuples in memory)

A ~30% speedup in the expensive cases, very impressive!

Replying to tscrim:

I also changed the r = 10 case to not be accepted for the index naming because you are using 1-based indices.

I left the cutoff at 11 because I figured technically a zero does not cause ambiguity since it must always be attached to a 10. For aesthetic and convenience the cutoff at 10 is much better though.

The changes all look very good to me, thanks for the improvements!

comment:12 Changed 4 years ago by vbraun

  • Branch changed from public/lie_algebras/free_nilpotent-26076 to 664fbeceb2594310cb95ffe1df434e41ceb5ebbd
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.