## ~jmbr/cl-buchberger

Buchberger's algorithm in Common Lisp
`Style fixes.`
`Simplify loop bounds.`
`Represent set of pairs of indices as a hash table.`

main
browse  log

### clone

https://git.sr.ht/~jmbr/cl-buchberger
git@git.sr.ht:~jmbr/cl-buchberger

You can also use your local clone with git send-email.

## #cl-buchberger

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

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.