cl-buchberger

Common Lisp implementation of Buchberger's algorithm.

Overview

cl-buchberger is a Common Lisp implementation of Buchberger's algorithm for the computation of Gröbner bases.

This package computes Gröbner bases of ideals in multivariate polynomial rings over the rationals. Gröbner bases are often used for solving systems of polynomial equations and have further applications in automated theorem proving, graph coloring, etc.

Usage

Installing and loading the package

To install or load cl-buchberger using Quicklisp, write:

CL-USER> (ql:quickload :cl-buchberger)
...
CL-USER> (in-package :cl-buchberger-user)
#<PACKAGE "CL-BUCHBERGER-USER">

Defining a polynomial ring

The default ring is the ring of polynomials on X, Y, Z over the rationals and is available as the dynamic variable *RING*. To define custom polynomial rings use:

CL-BUCHBERGER-USER> (make-instance 'polynomial-ring :variables
                                   '(x y z u w r s))
#<POLYNOMIAL-RING :VARIABLES (X Y Z U W R S) :BASE-FIELD RATIONAL>

To change the default ring just bind *RING* to another instance of POLYNOMIAL-RING:

CL-BUCHBERGER-USER> (defparameter *ring*
                      (make-instance 'polynomial-ring :variables '(x y))
                      "ℚ[x, y]")
*RING*
CL-BUCHBERGER-USER> *ring*
#<POLYNOMIAL-RING :VARIABLES (X Y) :BASE-FIELD RATIONAL>

Defining polynomials

Polynomials are defined using s-expressions. For example,

(x (expt y 2) (expt z 3))

corresponds to the monomial xy²z³.

The following code defines two polynomials named *l* and *m*,

CL-BUCHBERGER-USER> (defparameter *l*
                      (make-polynomial '(- (expt x 3) (* 2 x y))))
*L*
CL-BUCHBERGER-USER> *l*
#<POLYNOMIAL x^3 - 2xy>
CL-BUCHBERGER-USER> (defparameter *m*
                      (make-polynomial '(+ (* 3 (expt x 4) y) (expt x 2))))
*M*
CL-BUCHBERGER-USER> *m*
#<POLYNOMIAL 3x^4y + x^2>

Polynomial arithmetic

Use the generic functions RING+, RING-, RING*, and RING/ for the usual arithmetic operations.

The function RING/ is the multivariate polynomial division algorithm. It takes a polynomial and a sequence of divisors as input and it outputs a sequence of quotients and a remainder.

To set the default monomial ordering, bind *MONOMIAL-ORDERING* to the desired ordering function (the default is LEX>). For example:

CL-BUCHBERGER-USER> (defparameter *monomial-ordering* #'grevlex>)
*MONOMIAL-ORDERING*

You may also use the macro WITH-MONOMIAL-ORDERING to set the current monomial ordering as in:

CL-BUCHBERGER-USER> (with-monomial-ordering #'grlex>
                      (ring/ *m* *l*))
#(#<POLYNOMIAL 3xy>)
#<POLYNOMIAL 6x^2y^2 + x^2>

Computing Gröbner bases

The functions GROEBNER and REDUCED-GROEBNER compute Gröbner bases and reduced Gröbner bases respectively. Both of them take a sequence of polynomials as their argument. Alternatively, one may construct a polynomial ideal and obtain its reduced Gröbner basis using the BASIS generic function.

For example:

CL-BUCHBERGER-USER> (defparameter *ring* (make-instance 'polynomial-ring
                                                        :variables '(x y z)))
*RING*
CL-BUCHBERGER-USER> (defparameter *katsura-3*
                      (make-ideal (make-polynomial '(+ x (* 2 y) (* 2 z) -1))
                                  (make-polynomial '(+ (expt x 2) (- x)
                                                       (* 2 (expt y 2))
                                                       (* 2 (expt z 2))))
                                  (make-polynomial '(+ (* 2 x y) (* 2 y z)
                                                       (- y))))
                      "Katsura-3 over ℚ[x, y, z] (default ring)")
*KATSURA-3*
CL-BUCHBERGER-USER> *katsura-3*
#<IDEAL :RING #<POLYNOMIAL-RING :VARIABLES (X Y Z) :BASE-FIELD RATIONAL>
        :GENERATORS #(#<POLYNOMIAL x + 2y + 2z - 1>
                      #<POLYNOMIAL x^2 - x + 2y^2 + 2z^2>
                      #<POLYNOMIAL 2xy + 2yz - y>)>
CL-BUCHBERGER-USER> (with-monomial-ordering #'lex>
                      (basis *katsura-3*))
#(#<POLYNOMIAL x - 60z^3 + 158/7z^2 + 8/7z - 1>
  #<POLYNOMIAL y + 30z^3 - 79/7z^2 + 3/7z>
  #<POLYNOMIAL z^4 - 10/21z^3 + 1/84z^2 + 1/84z>)

Contributing

The mailing list cl-buchberger-devel is for development discussion and patches related to this project. For help sending patches to this list, please consult git-send-email.io.