Efficiently compute Kronecker coefficients of bounded height

barvikron is a Python implementation of an efficient algorithm for computing Kronecker coefficients proposed by Christandl-Doran-Walter (2012). Kronecker coefficients play an important role in combinatorics, quantum physics and geometric complexity theory. Their computation is known to be #P-hard in general. Given partitions with a bounded number of rows, however, our algorithm based on lattice-point counting computes the corresponding Kronecker coefficient in polynomial time.

If you find barvikron useful in your research please consider citing our paper:

@Inproceedings{barvikron,
  Author    = {Christandl, M. and Doran, B. and Walter, M.},
  Title     = {{Computing Multiplicities of Lie Group Representations}},
  Booktitle = {2012 IEEE 53rd Annual Symposium on Foundations of Computer Science (FOCS)},
  Doi       = {10.1109/FOCS.2012.43},
  Pages     = {639--648},
  Year      = {2012},
  Note      = {Software available at \url{https://github.com/catch22/barvikron/}.},
}

To install barvikron, simply run:

pip install git+git://github.com/catch22/barvikron.git

Then install either barvinok or LattE.

To compute a single Kronecker coefficient, call barvikron with the partitions and specify either the barvinok or LattE backend:

$ barvikron [4096,4096] [4096,4096] [4096,4096] --barvinok /opt/barvinok/bin/barvinok_count 
1

barvikron can also be used as a Python library:

import barvikron

e = barvikron.BarvinokEvaluator('/opt/barvinok/bin/barvinok_count')
g = barvikron.kronecker([[3,1], [3,1], [2,2]], e)
print(g)  # prints 1

Usage: barvikron [OPTIONS] λ μ ν ...

  Compute (generalized) Kronecker coefficient g(λ,μ,ν,...).

Options:
  --barvinok PATH        Path to barvinok_count tool (see
                         http://barvinok.gforge.inria.fr/).
  --latte PATH           Path to LattE's count tool (see
                         https://www.math.ucdavis.edu/~latte/).
  --weight-multiplicity  Compute weight multiplicity instead of Kronecker
                         coefficient.
  -v, --verbose
  --help                 Show this message and exit.

There are two parts. First, there is the "master" process, which is run once:

Usage: barvikron-master [OPTIONS] λ μ ν ...

  Compute (generalized) Kronecker coefficient g(λ,μ,ν,...) using parallel
  processing. See README for instructions.

Options:
  -P, --port INTEGER  Port to listen at for communication with workers.
  -K, --authkey TEXT  Secret authentication key for communication with
                      workers.  [required]
  -v, --verbose
  --help              Show this message and exit.

It hands off the weight multiplicity computations to worker processes that should be run on the computational nodes (optimally, one process per core of each node).

Usage: barvikron-worker [OPTIONS] λ μ ν ...

  Compute (generalized) Kronecker coefficient g(λ,μ,ν,...) using parallel
  processing. See README for instructions.

Options:
  -H, --host TEXT     Hostname of master.  [required]
  -P, --port INTEGER  Port to connect to for communication with master.
  -K, --authkey TEXT  Secret authentication key for communication with
                      workers.  [required]
  --barvinok PATH     Path to barvinok_count tool (see
                      http://barvinok.gforge.inria.fr/).
  --latte PATH        Path to LattE's count tool (see
                      https://www.math.ucdavis.edu/~latte/).
  -v, --verbose
  --help              Show this message and exit.

In this way, Kronecker coefficients can be computed in a massively parallel fashion.

Here is a sample script for computing Kronecker coefficients using the LSF platform:

#!/bin/bash
PARTITIONS="[40000,20000,10000] [50000,10000,10000] [30000,20000,20000]"
barvikron-master $PARTITIONS -K SECRET -v &
blaunch -z "$LSB_HOSTS" barvikron-worker -H "$HOSTNAME" -K SECRET $PARTITIONS --barvinok $PATH_TO_BARVINOK -v

Barvikron is much faster than codes such as LiE or Sage's symmetric function library for computing Kronecker coefficients with long rows. Here are some preliminary benchmarking results for computing the family of three-row Kronecker coefficients g_{N * [4,2,1], N * [5,1,1], N * [3,2,2]} using a varying number of processors (of type Opteron6174).

We note that evaluating each such Kronecker coefficient amounts to evaluating 216 weight multiplicities for GL(3) x GL(3) x GL(3). Computing a single weight multiplicity takes 3m25.701s and 4m7.178s for N = 10000 and 100000, respectively.

Interestingly, the weight multiplicity of [400000,200000,100000], [500000,100000,100000], [300000,200000,200000] in Sym^700000(C^27) is equal to 342216835855298841170737708279176303674277186351573308277640173317403784744358278942583775... 😄

— Michael Walter, 2012–2016