Buchberger's algorithm in Common Lisp

52f12e5 Style fixes.

~jmbr pushed to ~jmbr/cl-buchberger git

2 months ago

5f2d903 Simplify loop bounds.

~jmbr pushed to ~jmbr/cl-buchberger git

2 months ago


#Common Lisp implementation of Buchberger's algorithm.


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.


#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)

#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))

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]")

#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))))
#<POLYNOMIAL x^3 - 2xy>
CL-BUCHBERGER-USER> (defparameter *m*
                      (make-polynomial '(+ (* 3 (expt x 4) y) (expt x 2))))
#<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>)

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)))
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)")
        :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>)


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.