Bug in Lie algebra's chevalley_eilenberg_complex method

[DaveWitteMorris]

As pointed out in this sage_devel thread, the Lie algebra method chevalley_eilenberg_complex() raises an exception in the following example:

sage: g = lie_algebras.sl(QQ,2)
sage: E,F,H = g.basis()
sage: n = g.subalgebra([F,H])
sage: n.chevalley_eilenberg_complex()
Exception raised by child process with pid=15420:
Traceback (most recent call last):
  File "sage/misc/cachefunc.pyx", line 1943, in sage.misc.cachefunc.CachedMethodCaller.__call__ (build/cythonized/sage/misc/cachefunc.c:10414)
    return cache[k]
KeyError: (None, False, True)

During handling of the above exception, another exception occurred:
    <snip>
~/development/sage94/local/var/lib/sage/venv-python3.9/lib/python3.9/site-packages/sage/homology/chain_complex.py in <genexpr>(.0)
    259             base_ring = ZZ
    260         else:
--> 261             bases = tuple(x.base_ring() for x in data_dict.values())
    262             base_ring = coercion_model.common_parent(*bases)
    263 

AttributeError: 'str' object has no attribute 'base_ring'

CC: @tscrim @fchapoton

Component: algebra

Keywords: Lie algebra

Author: Travis Scrimshaw

Branch/Commit: 8526fe9

Reviewer: Sebastian Oehms

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

[DaveWitteMorris]

comment:1

The KeyError does not seem to be a bug, because it arises in a try block (where the code is checking whether the desired value is available in the cache). The AttributeError is raised in the corresponding except block, and seems to reveal a genuine problem: at the time of this exception, data_dict is equal to {1: [0 0], 2: 'NO DATA'}.

[DaveWitteMorris]

Changed keywords from lie algebra to Lie algebra

[tscrim]

comment:2

Thanks for the summary. I will try to look at this next month; right now I am traveling and then I will be moving universities. If someone else is able to fix it, I can likely do a quick review. However, I likely won’t have time to debug it for now.

[tscrim]

comment:3

I have a little bit of time and I found the source of the bug: the to_vector() returns a vector based on the ambient space:

sage: n.an_element()
h1
sage: _.to_vector()
(0, 1, 0)

We don't want to change this as the (linear algebraic) model for this is a subspace of a vector space:

sage: _.parent()
Vector space of degree 3 and dimension 2 over Rational Field
User basis matrix:
[0 1 0]
[0 0 1]

So we just need to remove an assumption that the length of the vector equals the dimension of the vector space.

[tscrim]

Commit: aeabb7f

[tscrim]

Branch: public/lie_algebras/fix_ce_complex-33836

[tscrim]

Author: Travis Scrimshaw

[tscrim]

comment:4

Okay, here is a fix that converts the vector to something of the correct length when working with a submodule. Timings (run with 1 core for more expressive timings):

sage: g = lie_algebras.sl(QQ,2)  # 3 dim
sage: %time g.chevalley_eilenberg_complex(ncpus=1)
CPU times: user 16 ms, sys: 12 ms, total: 28 ms
Wall time: 68.4 ms
sage: g = lie_algebras.sp(QQ,4)  # 10 dim
sage: %time g.chevalley_eilenberg_complex(ncpus=1)
CPU times: user 24 ms, sys: 56 ms, total: 80 ms
Wall time: 612 ms
Chain complex with at most 11 nonzero terms over Rational Field
sage: g = lie_algebras.sl(QQ,4)  # 15 dim
sage: %time g.chevalley_eilenberg_complex(ncpus=1)
CPU times: user 35 s, sys: 188 ms, total: 35.1 s
Wall time: 1min 12s

versus before

sage: g = lie_algebras.sl(QQ,2)  # 3 dim
sage: %time g.chevalley_eilenberg_complex(ncpus=1)
CPU times: user 16 ms, sys: 12 ms, total: 28 ms
Wall time: 67.2 ms
sage: g = lie_algebras.sp(QQ,4)  # 10 dim
sage: %time g.chevalley_eilenberg_complex(ncpus=1)
CPU times: user 36 ms, sys: 48 ms, total: 84 ms
Wall time: 577 ms
sage: g = lie_algebras.sl(QQ,4)  # 15 dim
sage: %time g.chevalley_eilenberg_complex(ncpus=1)
CPU times: user 31.8 s, sys: 124 ms, total: 31.9 s
Wall time: 1min 6s

So there is some slowdown likely between 5-10%, but it can't be helped because the code needs to work.

---

New commits:

aeabb7f

Changing CE-complex to use monomial_coefficients() instead of to_vector() for computation.

[tscrim]

comment:5

See also #34006 for a related issue.

[sagetrac-git]

Changed commit from aeabb7f to d0b745d

[sagetrac-git]

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

d0b745d

Merge branch 'public/lie_algebras/fix_ce_complex-33836' of https://github.com/sagemath/sagetrac-mirror into public/lie_algebras/fix_ce_complex-33836

[soehms]

comment:7

Replying to @tscrim:

So there is some slowdown likely between 5-10%,

I'm wondering about that! There is only one if condition on a boolean in addition (of course in a long for loop). Maybe this 5-10% have been caused by some external influences. I repeated your test (on an i7 CPU running under WSL). The first and the last example were even slower without the ticket:

With the ticket:

sage: g = lie_algebras.sl(QQ,2)  # 3 dim
sage: %time g.chevalley_eilenberg_complex(ncpus=1)
CPU times: user 0 ns, sys: 18.4 ms, total: 18.4 ms
Wall time: 44.5 ms
Chain complex with at most 4 nonzero terms over Rational Field
sage: g = lie_algebras.sp(QQ,4)  # 10 dim
sage: %time g.chevalley_eilenberg_complex(ncpus=1)
CPU times: user 50.5 ms, sys: 30.1 ms, total: 80.6 ms
Wall time: 443 ms
Chain complex with at most 11 nonzero terms over Rational Field
sage: g = lie_algebras.sl(QQ,4)  # 15 dim
sage: %time g.chevalley_eilenberg_complex(ncpus=1)
CPU times: user 13.6 s, sys: 88 ms, total: 13.7 s
Wall time: 28.7 s
Chain complex with at most 16 nonzero terms over Rational Field

Without the ticket:

sage: g = lie_algebras.sl(QQ,2)  # 3 dim
sage: %time g.chevalley_eilenberg_complex(ncpus=1)
CPU times: user 11.1 ms, sys: 11.3 ms, total: 22.4 ms
Wall time: 52.8 ms
Chain complex with at most 4 nonzero terms over Rational Field
sage: g = lie_algebras.sp(QQ,4)  # 10 dim
sage: %time g.chevalley_eilenberg_complex(ncpus=1)
CPU times: user 58.4 ms, sys: 20.6 ms, total: 79 ms
Wall time: 435 ms
Chain complex with at most 11 nonzero terms over Rational Field
sage: g = lie_algebras.sl(QQ,4)  # 15 dim
sage: %time g.chevalley_eilenberg_complex(ncpus=1)
CPU times: user 13.8 s, sys: 7.25 ms, total: 13.9 s
Wall time: 29 s
Chain complex with at most 16 nonzero terms over Rational Field

Anyway, you should add a test showing that the issue is fixed.

[sagetrac-git]

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

8526fe9

Adding doctest and one other small tweak for speed.

[sagetrac-git]

Changed commit from d0b745d to 8526fe9

[tscrim]

comment:9

Replying to @soehms:

Replying to @tscrim:

So there is some slowdown likely between 5-10%,

I'm wondering about that! There is only one if condition on a boolean in addition (of course in a long for loop). Maybe this 5-10% have been caused by some external influences. I repeated your test (on an i7 CPU running under WSL). The first and the last example were even slower without the ticket:

Hmm...interesting. Well, either way, a bug has been fixed.

Anyway, you should add a test showing that the issue is fixed.

Done. I also made one other small tweak for speed.

[soehms]

Reviewer: Sebastian Oehms

[soehms]

comment:10

Replying to @tscrim:

Replying to @soehms:

Replying to @tscrim:

So there is some slowdown likely between 5-10%,

I'm wondering about that! There is only one if condition on a boolean in addition (of course in a long for loop). Maybe this 5-10% have been caused by some external influences. I repeated your test (on an i7 CPU running under WSL). The first and the last example were even slower without the ticket:

Hmm...interesting. Well, either way, a bug has been fixed.

Anyway, you should add a test showing that the issue is fixed.

Done. I also made one other small tweak for speed.

LGTM! Once there is a green patchbot we can set positive review-

[soehms]

comment:11

Once there is a green patchbot we can set positive review

Now, there is just one failure in the current patchbot log-file which is obviously unrelated to the ticket.

[tscrim]

comment:12

Thank you.

[vbraun]

Changed branch from public/lie_algebras/fix_ce_complex-33836 to 8526fe9