# 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 @[email protected] 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>)
```

You are viewing proxied material from tilde.institute. The copyright of proxied material belongs to its original authors. Any comments or complaints in relation to proxied material should be directed to the original authors of the content concerned. Please see the disclaimer for more details.