https://github.com/jmbr/cl-buchberger.git
git clone 'https://github.com/jmbr/cl-buchberger.git'
(ql:quickload :cl-buchberger)
Juan M. Bello Rivas mailto:jmbr@superadditive.com June 2009
image::images/cl-buchberger.png[Screenshot]
cl-buchberger is a Common Lisp implementation of Buchberger's algorithm for the computation of Gröbner bases.
Currently this package can compute Gröbner bases of ideals in multivariate polynomial rings over the rationals.
Download the latest version of this package from http://github.com/jmbr/cl-buchberger/tarball/master
The code has been tested under
cl-buchberger is released under the GNU GPLv2.
Loading the package ~~~~~~~~~~~~~~~~~~~
You need ASDF installed in your system. To load cl-buchberger, write:
—————————————————— CL-USER> (asdf:operate 'asdf:load-op :cl-buchberger) NIL CL-USER> (use-package :cl-buchberger) T ——————————————————
Defining a polynomial ring ~~~~~~~~~~~~~~~~~~~~~~~~~~
There's a default ring which is the ring of polynomials on X, Y, Z over the rationals. To define custom polynomial rings use:
——————————————————— CL-USER> (make-instance 'polynomial-ring :variables (list 'x 'y 'z 'u 'w 'r 's 't)) #<POLYNOMIAL-RING X, Y, Z, U, W, R, S, T over RATIONAL> ———————————————————
To change the default ring just bind *RING* to whatever you want:
——————————————————————— CL-USER> (defparameter ring (make-instance 'polynomial-ring :variables (list 'x 'y)) “QQ[X, Y]”) RING CL-USER> ring #<POLYNOMIAL-RING X, Y over RATIONAL> ———————————————————————
Defining polynomials ~~~~~~~~~~~~~~~~~~~~
Polynomials are defined using a list of terms where each term is a
list with the coefficient as its first term and where the remaining
elements are variable exponents. For example: (1 1 2 3) would
correspond to the term $$xy^2z^3$$
Thus, to create a polynomial write:
——————————————————————- CL-USER> (defparameter l (make-polynomial ‘((1 3 0) (-2 1 1)))) L CL-USER> l #<POLYNOMIAL x^3 - 2xy> CL-USER> (defparameter m (make-polynomial ’((3 4 1) (1 2 0)))) M CL-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 and takes a polynomial and a sequence of divisors to produce a sequence of quotients and a remainder.
To set the default monomial ordering, bind *MONOMIAL-ORDERING* to the relevant function (which defaults to LEX>). For example:
——————————————————– CL-USER> (defparameter monomial-ordering #'grevlex>) MONOMIAL-ORDERING ——————————————————–
Also, you can use the macro WITH-MONOMIAL-ORDERING to define the current monomial ordering as in:
——————————————-
CL-USER> (with-monomial-ordering #'grlex>
(ring/ m l))
#(#
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 parameter. An alternative is to construct a polynomial ideal and obtain its reduced Gröbner basis using the BASIS generic function.
For example:
——————————————————————————– CL-USER> (defparameter katsura-3 (make-ideal (list (make-polynomial ‘((1 1 0 0) (2 0 1 0) (2 0 0 1) (-1 0 0 0))) (make-polynomial ’((1 2 0 0) (-1 1 0 0) (2 0 2 0) (2 0 0 2))) (make-polynomial '((2 1 1 0) (2 0 1 1) (-1 0 1 0))))) “Katsura-3 over QQ[x, y, z] (default ring)”) KATSURA-3 CL-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-USER> (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>) ——————————————————————————–
There's a bug tracker available at http://github.com/jmbr/cl-buchberger/issues