# The cl-buchberger Reference Manual

Next: , Previous: , Up: (dir)   [Contents][Index]

# The cl-buchberger Reference Manual

This is the cl-buchberger Reference Manual, version 0.0.4, generated automatically by Declt version 2.4 "Will Decker" on Wed Jun 20 10:59:49 2018 GMT+0.

Next: , Previous: , Up: Top   [Contents][Index]

## 1 Introduction

```cl-buchberger
=============
Juan M. Bello Rivas
June 2009

image::images/cl-buchberger.png[Screenshot]

Overview
--------

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.

Availability
------------

http://github.com/jmbr/cl-buchberger/tarball/master

Portability
-----------

The code has been tested under

1. ABCL 0.16.0-dev
2. CLISP 2.47
3. ECL 9.6.1
4. SBCL 1.0.29

-------

cl-buchberger is released under the GNU GPLv2.

Usage
-----

~~~~~~~~~~~~~~~~~~~

write:

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

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

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*
#
CL-USER> (defparameter *m* (make-polynomial '((3 4 1) (1 2 0))))
*M*
CL-USER> *m*
#
-------------------------------------------------------------------

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*
# :GENERATORS #(#
#
#)>
CL-USER> (basis *katsura-3*)
#(#
#
#)
--------------------------------------------------------------------------------

Bug reports
-----------

There's a bug tracker available at http://github.com/jmbr/cl-buchberger/issues

```

Next: , Previous: , Up: Top   [Contents][Index]

## 2 Systems

The main system appears first, followed by any subsystem dependency.

Previous: , Up: Systems   [Contents][Index]

### 2.1 cl-buchberger

Author

GNU GPLv2

Description

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

Version

0.0.4

Source

cl-buchberger.asd (file)

Components

Next: , Previous: , Up: Top   [Contents][Index]

## 3 Files

Files are sorted by type and then listed depth-first from the systems components trees.

Previous: , Up: Files   [Contents][Index]

### 3.1 Lisp

Next: , Previous: , Up: Lisp files   [Contents][Index]

#### 3.1.1 cl-buchberger.asd

Location

cl-buchberger.asd

Systems

cl-buchberger (system)

Packages

Next: , Previous: , Up: Lisp files   [Contents][Index]

#### 3.1.2 cl-buchberger/package.lisp

Parent

cl-buchberger (system)

Location

package.lisp

Packages

Next: , Previous: , Up: Lisp files   [Contents][Index]

#### 3.1.3 cl-buchberger/vector.lisp

Dependency

package.lisp (file)

Parent

cl-buchberger (system)

Location

vector.lisp

Internal Definitions

#### 3.1.4 cl-buchberger/ring.lisp

Dependency

vector.lisp (file)

Parent

cl-buchberger (system)

Location

ring.lisp

Internal Definitions

ring (class)

Next: , Previous: , Up: Lisp files   [Contents][Index]

#### 3.1.5 cl-buchberger/ring-element.lisp

Dependency

ring.lisp (file)

Parent

cl-buchberger (system)

Location

ring-element.lisp

Exported Definitions
Internal Definitions

#### 3.1.6 cl-buchberger/term.lisp

Dependency

ring-element.lisp (file)

Parent

cl-buchberger (system)

Location

term.lisp

Exported Definitions
Internal Definitions

#### 3.1.7 cl-buchberger/monomial-orderings.lisp

Dependency

term.lisp (file)

Parent

cl-buchberger (system)

Location

monomial-orderings.lisp

Exported Definitions

#### 3.1.8 cl-buchberger/polynomial-ring.lisp

Dependency

monomial-orderings.lisp (file)

Parent

cl-buchberger (system)

Location

polynomial-ring.lisp

Exported Definitions
Internal Definitions

#### 3.1.9 cl-buchberger/polynomial.lisp

Dependency

polynomial-ring.lisp (file)

Parent

cl-buchberger (system)

Location

polynomial.lisp

Exported Definitions
Internal Definitions

#### 3.1.10 cl-buchberger/arithmetic.lisp

Dependency

polynomial.lisp (file)

Parent

cl-buchberger (system)

Location

arithmetic.lisp

Exported Definitions
Internal Definitions

#### 3.1.11 cl-buchberger/groebner.lisp

Dependency

arithmetic.lisp (file)

Parent

cl-buchberger (system)

Location

groebner.lisp

Exported Definitions
Internal Definitions

Previous: , Up: Lisp files   [Contents][Index]

#### 3.1.12 cl-buchberger/ideal.lisp

Dependency

groebner.lisp (file)

Parent

cl-buchberger (system)

Location

ideal.lisp

Exported Definitions
Internal Definitions

Next: , Previous: , Up: Top   [Contents][Index]

## 4 Packages

Packages are listed by definition order.

Next: , Previous: , Up: Packages   [Contents][Index]

Source

cl-buchberger.asd

Use List
• asdf/interface
• common-lisp

Source

package.lisp (file)

Nickname

cl-buchberger

Use List
• asdf/interface
• common-lisp
Exported Definitions
Internal Definitions

Next: , Previous: , Up: Top   [Contents][Index]

## 5 Definitions

Definitions are sorted by export status, category, package, and then by lexicographic order.

Next: , Previous: , Up: Definitions   [Contents][Index]

### 5.1 Exported definitions

Next: , Previous: , Up: Exported definitions   [Contents][Index]

#### 5.1.1 Special variables

Special Variable: *monomial-ordering*

Specifies the ordering of monomials in a polynomial

Package
Source

monomial-orderings.lisp (file)

Special Variable: *ring*

Default polynomial ring

Package
Source

polynomial-ring.lisp (file)

Next: , Previous: , Up: Exported definitions   [Contents][Index]

#### 5.1.2 Macros

Macro: doterms (VAR POLY &optional RESULTFORM) &body BODY
Package
Source

polynomial.lisp (file)

Macro: with-monomial-ordering ORDERING &body BODY
Package
Source

monomial-orderings.lisp (file)

Macro: with-polynomial-ring RING &body BODY
Package
Source

polynomial-ring.lisp (file)

Next: , Previous: , Up: Exported definitions   [Contents][Index]

#### 5.1.3 Functions

Function: degree M

Returns the total degree of a monomial

Package
Source

monomial-orderings.lisp (file)

Function: grevlex> M1 M2

Package
Source

monomial-orderings.lisp (file)

Function: grlex> M1 M2

Package
Source

monomial-orderings.lisp (file)

Function: groebner POLYNOMIALS

Returns a Groebner basis for the ideal generated by the specified array of polynomials.

Package
Source

groebner.lisp (file)

Function: lex> M1 M2

Lexicographic Order

Package
Source

monomial-orderings.lisp (file)

Function: make-ideal GENERATORS

Create a new ideal generated by the elements contained in the ‘generators’ list.

Package
Source

ideal.lisp (file)

Function: make-polynomial TERM-LIST &key RING
Package
Source

polynomial.lisp (file)

Function: mapterm FUNCTION POLYNOMIAL

Apply FUNCTION to successive terms of POLYNOMIAL. Return list of FUNCTION return values.

Package
Source

polynomial.lisp (file)

Function: reduce-gb G

Returns a reduced Groebner basis.

Package
Source

groebner.lisp (file)

Function: reduced-groebner F

Computes and reduces a Groebner basis of the ideal generated by F.

Package
Source

groebner.lisp (file)

Function: s-poly F G

Returns the S-polynomial of f and g

Package
Source

groebner.lisp (file)

Next: , Previous: , Up: Exported definitions   [Contents][Index]

#### 5.1.4 Generic functions

Generic Function: basis IDEAL

Returns an array of generators for ‘ideal’.

Package
Source

ideal.lisp (file)

Methods
Method: basis (IDEAL ideal)
Generic Function: lc POLY

Returns the leading coefficient of a polynomial

Package
Source

polynomial.lisp (file)

Methods
Method: lc (POLY polynomial)
Generic Function: lm POLY

Returns the leading monomial of a polynomial. That is, the leading term with 1 as coefficient

Package
Source

polynomial.lisp (file)

Methods
Method: lm (POLY polynomial)
Generic Function: lt POLY

Returns the leading term of a polynomial.

Package
Source

polynomial.lisp (file)

Methods
Method: lt (POLY polynomial)
Generic Function: member-p ELEMENT IDEAL
Package
Source

ideal.lisp (file)

Methods
Method: member-p (ELEMENT ring-element) (IDEAL ideal)
Generic Function: multideg POLY

Returns the multidegree of a polynomial

Package
Source

polynomial.lisp (file)

Methods
Method: multideg (POLY polynomial)
Generic Function: ring* ELEMENT &rest MORE-ELEMENTS
Package
Source

ring-element.lisp (file)

Methods
Method: ring* (POLY polynomial) &rest MORE-POLYNOMIALS
Source

arithmetic.lisp (file)

Generic Function: ring+ ELEMENT &rest MORE-ELEMENTS
Package
Source

ring-element.lisp (file)

Methods
Method: ring+ (POLY polynomial) &rest MORE-POLYNOMIALS
Source

arithmetic.lisp (file)

Generic Function: ring- ELEMENT &rest MORE-ELEMENTS
Package
Source

ring-element.lisp (file)

Methods
Method: ring- (POLY polynomial) &rest MORE-POLYNOMIALS
Source

arithmetic.lisp (file)

Generic Function: ring-equal-p E1 E2

Returns t if e1 equals e2, nil otherwise

Package
Source

ring-element.lisp (file)

Methods
Method: ring-equal-p (T1 term) (T2 term)
Source

term.lisp (file)

Generic Function: ring-identity-p ELEMENT

Returns t if element is the multiplicative identity, nil otherwise

Package
Source

ring-element.lisp (file)

Generic Function: ring-lcm E1 E2

Returns the LCM of e1 and e2

Package
Source

ring-element.lisp (file)

Methods
Method: ring-lcm (R1 rational) (R2 rational)

LCM over the rationals.

Source

arithmetic.lisp (file)

Method: ring-lcm (T1 term) (T2 term)

Returns LCM(t1, t2)

Source

arithmetic.lisp (file)

Generic Function: ring-zero-p ELEMENT

Returns t if element is zero, nil otherwise

Package
Source

ring-element.lisp (file)

Methods
Method: ring-zero-p (POLY polynomial)
Source

polynomial.lisp (file)

Method: ring-zero-p (TM term)
Source

term.lisp (file)

Generic Function: ring/ ELEMENT &rest MORE-ELEMENTS
Package
Source

ring-element.lisp (file)

Methods
Method: ring/ (POLY polynomial) &rest MORE-POLYNOMIALS
Source

arithmetic.lisp (file)

Previous: , Up: Exported definitions   [Contents][Index]

#### 5.1.5 Classes

Class: polynomial ()
Package
Source

polynomial.lisp (file)

Direct superclasses

ring-element (class)

Direct methods
Direct slots
Slot: base-ring
Initargs

:ring

Initform

(error "you must specify a base ring")

base-ring (generic function)

Writers

(setf base-ring) (generic function)

Slot: terms
Type

hash-table

Initargs

:terms

Initform

(make-hash-table :test (function equalp))

terms (generic function)

Writers

(setf terms) (generic function)

Class: polynomial-ring ()
Package
Source

polynomial-ring.lisp (file)

Direct superclasses

ring (class)

Direct methods
Direct slots
Slot: variables
Initargs

:variables

Initform

(error "you must specify at least one variable")

variables (generic function)

Slot: base-field
Initargs

:base-field

Initform

(quote rational)

base-field (generic function)

Previous: , Up: Definitions   [Contents][Index]

### 5.2 Internal definitions

Next: , Previous: , Up: Internal definitions   [Contents][Index]

#### 5.2.1 Functions

Function: criterion G B I J FI FJ

Returns t if S_{ij} has to be considered

Package
Source

groebner.lisp (file)

Function: make-index-set S
Package
Source

groebner.lisp (file)

Function: normal-form F G
Package
Source

groebner.lisp (file)

Function: pair-member L M B
Package
Source

groebner.lisp (file)

Function: terms->list POLY
Package
Source

polynomial.lisp (file)

Function: vector+ V1 V2

Returns the sum of the two vectors V1 and V2.

Package
Source

vector.lisp (file)

Function: vector- V1 V2

Returns the difference of the two vectors V1 and V2.

Package
Source

vector.lisp (file)

Function: vector-zero-p V

Returns T if every compoment in V is zero.

Package
Source

vector.lisp (file)

Function: vector= V1 V2

Returns T if both vectors V1 and V2 have the same components, NIL otherwise.

Package
Source

vector.lisp (file)

Function: vector> V1 V2

Returns T if every component in V1 is greater than the corresponding component in V2, NIL otherwise.

Package
Source

vector.lisp (file)

Next: , Previous: , Up: Internal definitions   [Contents][Index]

#### 5.2.2 Generic functions

Package
Source

ring-element.lisp (file)

Methods
Method: add (P1 polynomial) (P2 polynomial)

Returns the sum of two polynomials

Source

arithmetic.lisp (file)

Method: add (POLY polynomial) (TM term)

Returns the polynomial with the added term

Source

arithmetic.lisp (file)

Generic Function: base-field OBJECT
Package
Methods
Method: base-field (POLYNOMIAL-RING polynomial-ring)

Source

polynomial-ring.lisp (file)

Generic Function: base-ring OBJECT
Generic Function: (setf base-ring) NEW-VALUE OBJECT
Package
Methods
Method: base-ring (POLYNOMIAL polynomial)

Source

polynomial.lisp (file)

Method: (setf base-ring) NEW-VALUE (POLYNOMIAL polynomial)

automatically generated writer method

Source

polynomial.lisp (file)

Generic Function: coefficient OBJECT
Generic Function: (setf coefficient) NEW-VALUE OBJECT
Package
Methods
Method: coefficient (TERM term)

Source

term.lisp (file)

Method: (setf coefficient) NEW-VALUE (TERM term)

automatically generated writer method

Source

term.lisp (file)

Generic Function: div E1 E2

Divides ring elements

Package
Source

ring-element.lisp (file)

Methods
Method: div (T1 term) (T2 term)

Returns the quotient of two terms

Source

arithmetic.lisp (file)

Generic Function: divides-p E1 E2

Returns t if e1 divides e2 in the base ring

Package
Source

ring-element.lisp (file)

Methods
Method: divides-p (T1 term) (P polynomial)
Source

arithmetic.lisp (file)

Method: divides-p (T1 term) (T2 term)
Source

arithmetic.lisp (file)

Generic Function: divmod ELEMENT DIVISORS

Returns quotient(s) and remainder if we are working in an Euclidean ring.

Package
Source

ring-element.lisp (file)

Methods
Method: divmod (F polynomial) FS

Divides F by the polynomials in the sequence FS and returns the quotients (as an array) and a remainder.

Source

arithmetic.lisp (file)

Generic Function: element->string ELEMENT &key RING LEADING-TERM &allow-other-keys

Returns a human-readable string representation of an element

Package
Source

ring-element.lisp (file)

Methods
Method: element->string (POLY polynomial) &key
Source

polynomial.lisp (file)

Method: element->string (TM term) &key RING LEADING-TERM
Source

term.lisp (file)

Generic Function: generators OBJECT
Generic Function: (setf generators) NEW-VALUE OBJECT
Package
Methods
Method: generators (IDEAL ideal)

Source

ideal.lisp (file)

Method: (setf generators) NEW-VALUE (IDEAL ideal)

automatically generated writer method

Source

ideal.lisp (file)

Generic Function: monomial OBJECT
Generic Function: (setf monomial) NEW-VALUE OBJECT
Package
Methods
Method: monomial (TERM term)

Source

term.lisp (file)

Method: (setf monomial) NEW-VALUE (TERM term)

automatically generated writer method

Source

term.lisp (file)

Generic Function: mul E1 E2

Multiplies ring elements

Package
Source

ring-element.lisp (file)

Methods
Method: mul (P1 polynomial) (P2 polynomial)

Returns the product of two polynomials

Source

arithmetic.lisp (file)

Method: mul (POLY polynomial) (TM term)

Returns the product of a polynomial by a term

Source

arithmetic.lisp (file)

Method: mul (T1 term) (T2 term)

Multiplies two terms storing the result in the first term.

Source

arithmetic.lisp (file)

Method: mul (T1 term) (NUM number)
Source

arithmetic.lisp (file)

Method: mul (POLY polynomial) (NUM number)
Source

arithmetic.lisp (file)

Generic Function: operands CONDITION
Package
Methods
Method: operands (CONDITION ring-division-by-zero)
Source

ring-element.lisp (file)

Generic Function: ring OBJECT
Generic Function: (setf ring) NEW-VALUE OBJECT
Package
Methods
Method: ring (IDEAL ideal)

Source

ideal.lisp (file)

Method: (setf ring) NEW-VALUE (IDEAL ideal)

automatically generated writer method

Source

ideal.lisp (file)

Generic Function: ring-copy ELEMENT

Returns a deep copy of an element

Package
Source

ring-element.lisp (file)

Methods
Method: ring-copy (POLY polynomial)

Returns a (deep) copy of the given polynomial

Source

polynomial.lisp (file)

Generic Function: ring-mod ELEMENT &rest MORE-ELEMENTS
Package
Source

ring-element.lisp (file)

Methods
Method: ring-mod F &rest FS
Source

arithmetic.lisp (file)

Generic Function: sub E1 E2

Subtracts ring elements

Package
Source

ring-element.lisp (file)

Methods
Method: sub (P1 polynomial) (P2 polynomial)

Returns the result of subtracting two polynomials.

Source

arithmetic.lisp (file)

Method: sub (POLY polynomial) (TM term)

Returns the result of subtracting the term from the polynomial

Source

arithmetic.lisp (file)

Generic Function: terms OBJECT
Generic Function: (setf terms) NEW-VALUE OBJECT
Package
Methods
Method: terms (POLYNOMIAL polynomial)

Source

polynomial.lisp (file)

Method: (setf terms) NEW-VALUE (POLYNOMIAL polynomial)

automatically generated writer method

Source

polynomial.lisp (file)

Generic Function: variables OBJECT
Package
Methods
Method: variables (POLYNOMIAL-RING polynomial-ring)

Source

polynomial-ring.lisp (file)

Next: , Previous: , Up: Internal definitions   [Contents][Index]

#### 5.2.3 Conditions

Condition: ring-division-by-zero ()
Package
Source

ring-element.lisp (file)

Direct superclasses

error (condition)

Direct methods

operands (method)

Direct slots
Slot: operands
Initargs

:operands

operands (generic function)

Previous: , Up: Internal definitions   [Contents][Index]

#### 5.2.4 Classes

Class: ideal ()
Package
Source

ideal.lisp (file)

Direct superclasses

standard-object (class)

Direct methods
Direct slots
Slot: ring
Initargs

:ring

Initform

(error "you must specify a ring for the polynomial ideal.")

ring (generic function)

Writers

(setf ring) (generic function)

Slot: generators
Initargs

:generators

Initform

(error "you must give a set of generators for the ideal.")

generators (generic function)

Writers

(setf generators) (generic function)

Class: ring ()

Base class for rings.

Package
Source

ring.lisp (file)

Direct superclasses

standard-object (class)

Direct subclasses

polynomial-ring (class)

Class: ring-element ()

Base class for ring elements.

Package
Source

ring-element.lisp (file)

Direct superclasses

standard-object (class)

Direct subclasses
Direct methods

member-p (method)

Direct slots
Slot: base-ring
Class: term ()
Package
Source

term.lisp (file)

Direct superclasses

ring-element (class)

Direct methods
Direct slots
Slot: coefficient
Initargs

:coefficient

Initform

0

coefficient (generic function)

Writers

(setf coefficient) (generic function)

Slot: monomial
Type

vector

Initargs

:monomial

monomial (generic function)

Writers

(setf monomial) (generic function)

Previous: , Up: Top   [Contents][Index]

## Appendix A Indexes

Next: , Previous: , Up: Indexes   [Contents][Index]

### A.1 Concepts

Next: , Previous: , Up: Indexes   [Contents][Index]

### A.2 Functions

Jump to: (   A   B   C   D   E   F   G   L   M   N   O   P   R   S   T   V   W
Jump to: (   A   B   C   D   E   F   G   L   M   N   O   P   R   S   T   V   W

Next: , Previous: , Up: Indexes   [Contents][Index]

### A.3 Variables

Jump to: *   B   C   G   M   O   R   S   T   V
Jump to: *   B   C   G   M   O   R   S   T   V

Previous: , Up: Indexes   [Contents][Index]