cl-buchberger: A Common Lisp implementation of Buchberger's algorithm.

cl-buchberger

# 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](https://www.quicklisp.org/), write:

```lisp
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:

```lisp
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`:

```lisp
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,
```lisp
(x (expt y 2) (expt z 3))
```
corresponds to the monomial xy²z³.

The following code defines two polynomials named `*l*` and `*m*`,
```lisp
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:

```lisp
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:

```lisp
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:

```lisp
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](https://lists.sr.ht/~jmbr/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](https://git-send-email.io).


cl-buchberger

Upstream URL

Author

License

cl-buchberger

License:

Authors:

Dependencies:

cl-buchberger/tests

License:

Authors:

Dependencies:

Dependencies (1)

Dependents (0)