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: |
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
comment:2 Changed 4 years ago by
- 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:
19c27eb | New subcategories of Lie algebras (nilpotent, graded, stratified) and a base class for nilpotent Lie algebras
|
f58cddd | Implementation of the construction of free nilpotent Lie algebras
|
cb8a103 | Changed doctests to use free nilpotent Lie algebras as more natural examples of graded or stratified Lie algebras
|
comment:3 Changed 4 years ago by
- Commit changed from cb8a1030ea0da83777e06bbf8aea9876819b2567 to 31fa53ab88a2d593f4fa2992f04d12e6f71f9930
Branch pushed to git repo; I updated commit sha1. Last 10 new commits:
158bfdb | Fix to product_space() for when L is not a true subalgebra of A.
|
293901e | Fixed a test for _test_generated_by_degree_one().
|
8658e9d | Fixing print order for fin-dim nilpotent Lie algebras with basis.
|
726639f | Some last little cleanup.
|
8b3c585 | A better failure example for _test_generated_by_degree_one and some more doc.
|
a1e1ace | Refactored nilpotent Lie algebra constructor into Lie algebra constructor
|
14fcd30 | Deduction rule for the fact that finite dimensional stratified Lie algebras are nilpotent
|
f1a0b1e | Docstring fix for indexing of grading of a stratification
|
4d4bdf6 | Merge remote-tracking branch 'trac/public/lie_algebras/base_class_nilponent-26074' into free_nilpotent_lie_algebras
|
31fa53a | Added free nilpotent Lie algebras to LieAlgebra constructor
|
comment:4 Changed 4 years ago by
- Commit changed from 31fa53ab88a2d593f4fa2992f04d12e6f71f9930 to b7c8a2a95b985b716a440bbdc89342528b5817ba
Branch pushed to git repo; I updated commit sha1. New commits:
a3dccfd | Merge branch 'public/lie_algebras/base_class_nilponent-26074' of git://trac.sagemath.org/sage into public/lie_algebras/base_class_nilponent-26074
|
0fa41ad | Fixing doctests, making category an arugment, and other small tweaks.
|
53a10be | Adding an extra doctest and fix for the category option.
|
d7077cd | Merge remote-tracking branch 'trac/public/lie_algebras/base_class_nilponent-26074' into u/gh-ehaka/free_nilpotent_lie_algebras-26076
|
b7c8a2a | Fixed category parameter of initialization of free nilpotent Lie algebra
|
comment:5 Changed 4 years ago by
- Commit changed from b7c8a2a95b985b716a440bbdc89342528b5817ba to 09b54f536e775b1f7c6b267ac25a77fbbdd52c99
comment:6 Changed 4 years ago by
- Commit changed from 09b54f536e775b1f7c6b267ac25a77fbbdd52c99 to b70bebd70696d8d22a58b422f90c701cb459f2db
Branch pushed to git repo; I updated commit sha1. New commits:
b70bebd | doctest fix for changed category printing
|
comment:7 Changed 4 years ago by
- 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:
8f7aac5 | Added missing files to documentation, removed non-existent one that was causing docbuild to fail
|
120c02a | Some trivial fixes.
|
7699db4 | Merge branch 'u/gh-ehaka/free_nilpotent_lie_algebras-26076' of git://trac.sagemath.org/sage into public/lie_algebras/free_nilpotent-26076
|
d1fe093 | Some reviewer changes and tweaks.
|
a60ef68 | Speedup constructor for free Nilpotent Lie algebras.
|
comment:8 Changed 4 years ago by
- Cc tscrim added
comment:9 Changed 4 years ago by
- Commit changed from a60ef683b3747b7d129b14b6834d0f329820a4fa to 664fbeceb2594310cb95ffe1df434e41ceb5ebbd
Branch pushed to git repo; I updated commit sha1. New commits:
664fbec | Changing r=10 as cutoff to requiring a linear ordering.
|
comment:10 follow-up: ↓ 11 Changed 4 years ago by
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
- 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
- Branch changed from public/lie_algebras/free_nilpotent-26076 to 664fbeceb2594310cb95ffe1df434e41ceb5ebbd
- Resolution set to fixed
- Status changed from positive_review to closed
Some implementation already exists in an external private codebase that I need to clean up and import into Sage.