# cl-buchberger
## Common Lisp implementation of Buchberger's algorithm.
### Juan M. Bello Rivas

## Screwtape's patched version

### Fixed make-polynomial and passing tests on ECL

#'MAKE-ARRAY in #'MAKE-POLYNOMIAL in src/polyomial.lisp
must have :initial-element '0 or it fills with NILs.

### package-inferred-system

Thank you to @svetlyak40wt@fosstodon.org on the mastodon for
reminding me to :depends-on my user packages in package-inferred-system 
and more!

I tried to systematically update the package style to

:class :package-inferred-system

Even though the dependencies weren't necessarily serial, I mostly attempted to
preserve the seriality so the change would purely be from

(:module code
 :pathname "src"
 :serial t
 :components ((:file "package")
              (:file "file1")
              (:file "file2") ..

in the defsystem to per file

(uiop:define-package :path/to/file2
 (:mix :cl)
 (:mix-reexport :path/to/file1)
 (:export <everything>))

 since each file/package needs to export to the other files. There are some 
 scraps of my confusion. :parser needed to be :import-from'ed instead.

One benefit is the possibility of (force re-) asdf:load-op'ing specific files 
while making changes like

(asdf:operate 'asdf:load-op "st-buchberger/src/parser" :force t)

screwtape out (Juan's original README continues)
..

(asdf:operate 'asdf:test-op :st-buchberger/tests)

passes both tests using SBCL on amd64 linux and openbsd. ECL is still broken.

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

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