Operads: Groebner basis computation for Operads.

[ bsd3, library, math ] [ Propose Tags ]

This is an implementation of the operadic Buchberger algorithm from Vladimir Dotsenko & Anton Khoroshkin: Groebner bases for operads (arXiv:0812.4069).

In writing this package, invaluable help has been given by Vladimir Dotsenko and Eric Hoffbeck.

The user is recommended to run this from within the GHC interpreter for exploration, and to write small Haskell scripts for batch processing. We hope herewithin to give enough of an overview of the available functionality to help the user figure out how to use the software package.

A declaration of a new variable is done in a Haskell script by a statement on the form

var = value

and in the interpreter by a statement on the form

let var = value

Using these, the following instructions should help get you started. I will be writing the instructions aiming for use in the interpreter, for quick starts.

It is possible to force types by following a declaration by :: and the type signature you'll which. This enables you, for instance, to pick a ground ring without having to set coefficients explicitly - see the examples below.

Note that the Buchberger algorithm in its current shape expects at least a division ring as scalar ring.

The expected workflow for a normal user is as follows.

  1. write the generators of the operadic ideal using corolla and leaf to construct buildingblocks and nsCompose, shuffleCompose and symmetricCompose to assemble them into trees. The trees, subsequently, may be assembled into tree polynomials by

  • picking an ordering. The orderings available are PathPerm, RPathPerm, PathRPerm, RPathRPerm, PermPath, RPermPath, PermRPath and RPermRPath, distinguished by reversal of order for either the path comparison or the permutation comparison, as well as by whether path or permutation comparison takes precedence.

  • assembling trees and coefficients into an element of the free operad, using + for addition of operadic elements and .*. for scalar multiplication.

Useful functions for doing this includes, furthermore:

takes a tree and an ordering and gives an operad element. You will have to specify the relevant type for this to work -- but we provide the extra type FreeOperad that only asks for a LabelType to cover most common uses:
oet tree :: OperadElement LabelType ScalarType TreeOrdering
takes a tree, an ordering and a coefficient and gives an operad element
oek tree PathPerm (3::Rational)


let t1 = nsCompose 1 (corolla a [2,1]) (corolla b [1,2])

let b = corolla l [1,2]

let lb1 = shuffleCompose 1 [1,2,3] b b

let lb2 = shuffleCompose 1 [1,3,2] b b

let lb3 = shuffleCompose 2 [1,2,3] b b

let lo1 = oet lb1 :: FreeOperad Char

let lo2 = oet lb2 :: FreeOperad Char

let lo3 = oet lb3 :: FreeOperad Char

Note that while the Haskell compiler in general is very skilled at guessing types of objects, the system guessing will give up if the type is not well defined. There are several different monomial orders allowed, and they are encoded in the type system -- hence the need to annotate the instantiation of elements in the free operad with appropriate types.

  1. assemble all generators into a list. Lists are formed by enclosing the elements, separated by commas, in square brackets. Lists must have identical type on all its elements - hence, for instance, you cannot have operadic elements with different monomial orderings in the same list.


let lgb = [lo1 - lo2 - lo3, 2.*.lo1 + 3.*. lo3]
  1. run the algorithm on your basis and wait for it to finish. The entry point to the Buchberger algorithm is, not surprisingly, operadicBuchberger.


let grobner = operadicBuchberger lgb

The output of operadicBuchberger, if it finishes, is a finite Gröbner basis for the ideal spanned by the original generators. If this is quadratic then the operad presented by this ideal is Koszul - this may be tested with something like:

all (==2) $ concatMap operationDegrees grobner

If you wish to inspect elements yourself, the recommended way to do it is by using the pP function, which outputs most of the interesting elements in a human-readable format. For objects that don't work with pP, just writing the variable name on its own will print it in some format.

The difference here is related to the ability to save computational states to disk. There are two different functions that will represent a tree or an element of an operad as a String: show and pp. Using the former guarantees (with the same version of the source code) that the data can be read back into the system and reused later one; whereas using pp will build a human readable string.

[Skip to Readme]




Automatic Flags

Use the Data.Map based storage for formal linear combinations.


Don't use the Data.Map wrapper class Math.Operad.Map. This will slow down computation.


Use -f <flag> to enable a flag, or -f -<flag> to disable that flag. More info


Maintainer's Corner

Package maintainers

For package maintainers and hackage trustees


  • No Candidates
Versions [RSS] 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 1.0
Change log CHANGELOG
Dependencies array, base (<=4), containers, mtl [details]
License BSD-3-Clause
Copyright © 2009 Mikael Vejdemo Johansson
Author Mikael Vejdemo Johansson
Maintainer mik@stanford.edu
Category Math
Home page http://math.stanford.edu/~mik/operads
Bug tracker mailto:mik@stanford.edu
Uploaded by MikaelVejdemoJohansson at 2009-08-14T13:23:10Z
Reverse Dependencies 1 direct, 0 indirect [details]
Downloads 6416 total (15 in the last 30 days)
Rating (no votes yet) [estimated by Bayesian average]
Your Rating
  • λ
  • λ
  • λ
Status Docs uploaded by user
Build status unknown [no reports yet]

Readme for Operads-1.0

[back to package description]
This Haskell software package implements the Gr�bner basis algorithm
as described in Vladimir Dotsenko, Anton Khoroshkin: "Gr�bner bases
for operads" (arXiv:0812.4096).

In order to use it, make sure you install ghc, cabal and haddock (see
http://haskell.org for more details). These are available directly in
most Linux and BSD distributions, and there are installers for MacOSX
and Windows available on http://haskell.org.

Once ghc is installed, install cabal-install, and then use that to
install everything else needed. This tool will make the installation
of everything else painless.

To install the package, download the most recent tar ball
Operads-n.n.tar.gz, and then perform the following steps:

1) copy the tarball into an appropriate temporary directory
2) in this temporary directory, execute 
     tar -xzvf Operads-n.n.tar.gz
3) enter the directory Operads-0.2
4) run the following commands
     ghc --make Setup.hs
     ./Setup configure
     ./Setup build
     ./Setup install
5) look through the example files
   to get a feeling for the syntax for interaction, and read the

   You can get a computation system by running
   and then inside ghci running
     :m + Math.Operad

   You can also write your own scripts for computation, and run them
   as Haskell programs. This will allow more latitude in using
   parallel processing and advanced computation techniques, but
   exceeds the scope of this README.

  * Make sure you run the program from somewhere else than the
    temporary building directory, as this would load the wrong files.