The Baker-Campbell-Hausdorff formula for nilpotent Lie algebras

[ehaka]

Computation of the Baker-Campbell-Hausdorff formula Z = log(exp(X)exp(Y)) in the case of nilpotent Lie algebras, where it reduces to a (complicated) polynomial expression.

Depends on #26076

Component: algebra

Keywords: Lie algebras, BCH formula

Author: Eero Hakavuori

Branch/Commit: 369f7a6

Reviewer: Travis Scrimshaw

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

[ehaka]

comment:1

Some implementation already exists in a codebase that I need to clean up and import into Sage. The method of computing is to compute the BCH formula for 2 generators of a free nilpotent Lie algebra of the same nilpotency step and to map the result to the desired nilpotent Lie algebra via a Lie algebra morphism mapping the generators to X and Y.

[ehaka]

Changed keywords from none to Lie algebras, BCH formula

[ehaka]

Author: Eero Hakavuori

[ehaka]

Changed dependencies from #26076, #26036 to #26076

[ehaka]

Branch: u/gh-ehaka/bch-26080

[ehaka]

comment:3

An initial implementation is in the commits. I ended up making the computation into an iterator returning the terms involving brackets of increasing lengths, so it is in theory possible to compute the BCH formula to arbitrary precision in any Lie algebra. I added a BCH method to LieAlgebras.Nilpotent to compute the full expression using this iterator.

The iterator might be of independent interest for the computation of the (low order terms of the) abstract BCH formula in a free Lie algebra, however I did not know what would be the best way to expose it to the user.

One unfortunate part is that the computation time becomes quite unwieldy for the later terms. For example on my computer, computing the terms of increasing degree for the free Lie algebra on 2 generators took the following times:

10 : 45.4 ms
11 : 116 ms
12 : 327 ms
13 : 1.08 s
14 : 4.2 s
15 : 16.3 s
16 : 1min 8s
17 : 4min 59s
18 : 20min 52s

The only more efficient algorithm I know of is the one of Casas-Murua (https://arxiv.org/abs/0810.2656). Based on their statement of requiring <15 mins for all terms of degree up to 20, I would guess that the efficiency improvement would be somewhere in the order of a 40x speed increase. For now, I think the simpler but less efficient approach is sufficient though.

---

New commits:

1276e0e

trac #26080: initial implementation of the BCH formula

[ehaka]

Commit: 1276e0e

[tscrim]

comment:4

Probably a good part of it might be a poor implementation of the Lie bracket for the free Lie algebra. At least it is taking on one iteration 14s/19s. Some caching, better implementation, and more Cythonization might help. At least, how it is currently designed is not very smart. For instance, it might be better to store the basis elements actually as lists that keeps track of the tree structure through some other list. There are definitely ways it can be improved (this is the first time that code is really being stress-tested for efficiency).

Anyways, I think this will work for now as we can always work on it more on a followup. Some comments on the code.

• I don't see the reason why the bch_formula should be a class. I think it would be better suited as just a generator function (i.e., using yield instead of return).

• Break the really long .. MATH:: line. Also avoid using \dots and instead be more specific about what kind of dots (in this case, \cdots) (I don't really trust \dots).

• You should have an alias baker_campbell_hausdorff = BCH. Also, Sage convention is still method names are generally lower cases, even for acronyms/last-names (e.g., it is pbw_basis, not PBW_basis).

• Instead of just having a method for nilpotent Lie algebras, I think it would be good to have one that allows for a "precision" to be inputted. For instance

  def bch(self, X, Y, prec=None):
      if self not in LieAlgebras.Nilpotent and prec is None:
          raise ValueError("the Lie algebra is not known to be nilpotent,"
                           " so you must specify the precision")
      from sage.algebras.lie_algebras.bch import BCH_iterator
      if prec is None:
          return self.sum(Z for Z in BCH_iterator(X, Y))
      bch = BCH_iterator(X, Y)
      return self.sum(next(bch) for k in range(prec))  # maybe prec+1?

[sagetrac-git]

Changed commit from 1276e0e to 5972b6b

[sagetrac-git]

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

5972b6b

trac #26080: converted bch iterator to a generator function and added interface for non-nilpotent Lie algebras