Ask Your Question
2

How to do low degree computation in a Free Algebra ?

asked 2021-01-14 16:03:58 +0100

qfaes gravatar image

updated 2021-01-15 16:47:35 +0100

slelievre gravatar image

Say $F$ is a free algebra over $n$ generators of degree $1$, and i want to compute in this algebra but i only need to get my expressions up to degree $k$. For example, if $k=2$, $(ab +a)*b$ should be $ab$.

For now, i have been doing the computation and truncating everything above degree $k$, but the time complexity is too high when i launch a big computation.

I am actually asking how to compute in the tensor Algebra $T(V)$ modulo $T_{\geq k}(V)$. For free Lie algebras, this can be done using nilpotent Lie algebras, (for example L = LieAlgebra(QQ, 3, step=3) implements a 3-nilpotent free Lie algebra). How to do this with free algebras ?

edit retag flag offensive close merge delete

2 Answers

Sort by ยป oldest newest most voted
2

answered 2021-01-15 22:50:28 +0100

slelievre gravatar image

updated 2021-01-18 15:57:18 +0100

Here is a function to produce the desired quotient algebra.

Given generator names, a maximum degree, and a base ring, it builds the free algebra on the generators with the requested names over the requested ring, and outputs the quotient modulo terms of degree higher than the specified maximum degree.

The following function works with one-letter generators.

def my_algebra(gen_names, max_degree=2, base_ring=QQ):
    r"""
    Return the quotient of the free algebra on these generators
    by terms of degree ``max_degree + 1``.
    """
    n = max_degree
    R = base_ring
    words = [w for W in [Words(gen_names, j) for j in range(n + 1)] for w in W]
    names = [str(w) for w in words[1:]]
    F = FreeAlgebra(R, names=names)
    FM = F.monoid()
    gens = FM.gens()
    mons = (FM.one(),) + gens
    r = len(mons)
    M = MatrixSpace(R, r)
    def row(m, mm):
        if len(m) + len(mm) > n:
            return [0] * r
        res = [0] * r
        res[words.index(mm * m)] = 1
        return res
    mats = [M([row(m, mm) for mm in words]) for m in words[1:]]
    return FreeAlgebraQuotient(F, mons, mats, names=names)

This variant accepts multicharacter generator names:

def my_algebra(gen_names, max_degree=2, base_ring=QQ):
    r"""
    Return the quotient of the free algebra on these generators
    by terms of degree ``max_degree + 1``.
    """
    n = max_degree
    R = base_ring
    word_options = dict(WordOptions())
    WordOptions(letter_separator='')
    words = [w for W in [Words(gen_names, j) for j in range(n + 1)] for w in W]
    names = [str(w) for w in words[1:]]
    F = FreeAlgebra(R, names=names)
    FM = F.monoid()
    gens = FM.gens()
    mons = (FM.one(),) + gens
    r = len(mons)
    M = MatrixSpace(R, r)
    def row(m, mm):
        if len(m) + len(mm) > n:
            return [0] * r
        res = [0] * r
        res[words.index(mm * m)] = 1
        return res
    mats = [M([row(m, mm) for mm in words]) for m in words[1:]]
    WordOptions(**word_options)
    return FreeAlgebraQuotient(F, mons, mats, names=names)

This function gives the multiplication table:

def algebra_table(G):
    gens = (G.one(),) + G.gens()
    prods = [[x * y for y in gens] for x in gens]
    hr = gens
    hc = ('*',) + gens
    return table(prods, header_row=hr, header_column=hc)

Some trials in the Sage REPL:

sage: G = my_algebra(['a', 'b'], max_degree=2, base_ring=QQ)
sage: a, b = G.gen(0), G.gen(1)
sage: (a * b + a) * b
ab

sage: algebra_table(G)
  *  | 1    a    b    aa   ab   ba   bb
+----+----+----+----+----+----+----+----+
  1  | 1    a    b    aa   ab   ba   bb
  a  | a    aa   ab   0    0    0    0
  b  | b    ba   bb   0    0    0    0
  aa | aa   0    0    0    0    0    0
  ab | ab   0    0    0    0    0    0
  ba | ba   0    0    0    0    0    0
  bb | bb   0    0    0    0    0    0

sage: G = my_algebra(['x1', 'x2'], max_degree=2, base_ring=QQ)
sage: a, b = G.gen(0), G.gen(1)
sage: (a * b + a) * b
x1x2

sage: algebra_table(G)
  *    | 1      x1     x2     x1x1   x1x2   x2x1   x2x2
+------+------+------+------+------+------+------+------+
  1    | 1      x1     x2     x1x1   x1x2   x2x1   x2x2
  x1   | x1     x1x1   x1x2   0      0      0      0
  x2   | x2     x2x1   x2x2   0      0      0      0
  x1x1 | x1x1   0      0      0      0      0      0
  x1x2 | x1x2   0      0      0      0      0      0
  x2x1 | x2x1   0      0      0      0      0      0
  x2x2 | x2x2   0      0      0      0      0      0

sage: G = my_algebra(['x_1', 'x_2'], max_degree=2, base_ring=QQ)
sage: a, b = G.gen(0), G.gen(1)
sage: (a * b + a) * b
x_1x_2

sage: algebra_table(G)
  *      | 1        x_1      x_2      x_1x_1   x_1x_2   x_2x_1   x_2x_2
+--------+--------+--------+--------+--------+--------+--------+--------+
  1      | 1        x_1      x_2      x_1x_1   x_1x_2   x_2x_1   x_2x_2
  x_1    | x_1      x_1x_1   x_1x_2   0        0        0        0
  x_2    | x_2      x_2x_1   x_2x_2   0        0        0        0
  x_1x_1 | x_1x_1   0        0        0        0        0        0
  x_1x_2 | x_1x_2   0        0        0        0        0        0
  x_2x_1 | x_2x_1   0        0        0        0        0        0
  x_2x_2 | x_2x_2   0        0        0        0        0        0

In Jupyter, latexing is off for names such as x1x2 or x_1x_2. Not sure how to fix that.

edit flag offensive delete link more

Comments

Thank you, it seems to answer my question, i ll try this tomorrow !

qfaes gravatar imageqfaes ( 2021-01-17 20:18:48 +0100 )edit

For now, the solution only works if your generators names are one letter (for example it does not work with x_1,x_2...).

EDIT : The solution for this is to add the command WordOptions(letter_separator='') before usinfg the words command in the code of slelievre.

qfaes gravatar imageqfaes ( 2021-01-18 11:25:30 +0100 )edit

Edited answer to partially address multicharacter generator names.

Sadly they are still not latexing properly.

slelievre gravatar imageslelievre ( 2021-01-18 15:58:25 +0100 )edit

Another way (less complete but more efficient for just a quick computation) is to compute directly in the Free algebra, but instead of using the product, use the following:

def fast_product(a,b): res = 0 a = F(a) b = F(b) data_a =[(w.to_word(), cf) for w, cf in a]
data_b =[(w.to_word(), cf) for w, cf in b] for wa,cfa in data_a: for wb,cfb in data_b: if len(wb) + len(wa) <= k: res = res + cfacfbF.monomial(wa)*F.monomial(wb)
return res

qfaes gravatar imageqfaes ( 2021-01-19 17:22:11 +0100 )edit

To format code blocks in questions, answers, or comments, separate them by a blank line above and below, and indent them by four spaces. Cay you edit your comment to do that?

Or you could turn your comment into an answer, since it actually answers the question.

slelievre gravatar imageslelievre ( 2021-01-19 21:14:50 +0100 )edit
2

answered 2021-01-22 15:28:06 +0100

qfaes gravatar image

updated 2021-01-22 18:34:31 +0100

slelievre gravatar image

Another way (less complete than @slelievre's answer but more efficient for just a quick computation) is to compute directly in the free algebra, using the following instead of the product:

def fast_product(a, b):
    res = F.zero()
    a = F(a)
    b = F(b)
    data_a = [(w.to_word(), cf) for w, cf in a] 
    data_b = [(w.to_word(), cf) for w, cf in b]
    for wa, cfa  in data_a:
        for wb, cfb in data_b:
            if len(wb) + len(wa) <= k:
                res += cfa * cfb * F.monomial(wa) * F.monomial(wb)  
    return res
edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

Stats

Asked: 2021-01-14 16:03:58 +0100

Seen: 82 times

Last updated: Jan 22