Opened 4 years ago
Closed 4 years ago
#26076 closed enhancement (fixed)
Free nilpotent Lie algebras
Reported by:  ghehaka  Owned by:  

Priority:  major  Milestone:  sage8.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/ghehaka/free_nilpotent_lie_algebras26076
 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 findim 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 remotetracking branch 'trac/public/lie_algebras/base_class_nilponent26074' 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_nilponent26074' of git://trac.sagemath.org/sage into public/lie_algebras/base_class_nilponent26074

0fa41ad  Fixing doctests, making category an arugment, and other small tweaks.

53a10be  Adding an extra doctest and fix for the category option.

d7077cd  Merge remotetracking branch 'trac/public/lie_algebras/base_class_nilponent26074' into u/ghehaka/free_nilpotent_lie_algebras26076

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/ghehaka/free_nilpotent_lie_algebras26076 to public/lie_algebras/free_nilpotent26076
 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 nonexistent one that was causing docbuild to fail

120c02a  Some trivial fixes.

7699db4  Merge branch 'u/ghehaka/free_nilpotent_lie_algebras26076' of git://trac.sagemath.org/sage into public/lie_algebras/free_nilpotent26076

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 followup: ↓ 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 1based 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 1based 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_nilpotent26076 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.