This is an (experimental) implementation of some methods of computer algebra in Haskell, in particular for the computation of Gröbner bases.

Features

The ComputerAlgebra library provides the type classes Ring, Algebra and RingWithDiv to represent the corresponding mathematical objects.

The RR type represents the real numbers and is essentially a small wrapper around Double, viewed as a ring. Similarly, QQ represents the rationals and ZZ the integers.

Monomial orders are represented by the MonOrder data type. The following monomial orders are provided:

• lexi_order: the lexicographic order
• graded_lexi_order: the graded lexicographic order
• grevlex_order: the graded reverse lexicographic order

Then one can construct graded polynomials as follows:

import ComputerAlgebra

-- The polynomial x^2 + 2xy + 3 y^2 with the lexicographic order x > y.
f_1 :: OrderedPolynomial RR
f_1 = make_ordered_poly (lexi_order [1,2]) [([2,0], RR 1), ([1,1], RR 2), ([0,2], RR 3)]

-- The polynomial y^2 + x^2 with the lexicographic order y > x.
f_2 :: OrderedPolynomial RR
f_2 = make_ordered_poly (lexi_order [2,1]) [([0,2], RR 1), ([2,0], RR 1)]

-- The polynomial xy with the lexicographic order y > x.
f_3 :: OrderedPolynomial RR
f_3 = make_ordered_poly (lexi_order [2,1]) [([1,1], RR 1)]

Using the GroebnerBases module, we can then use the function buchberger_algorithm to compute a Gröbner basis. Similarly, the compute_reduced_groebner_basis computes the (unique) reduced Gröbner basis.

import GroebnerBases
ex_1 = make_ordered_poly (lexi_order [3,2,1]) [([0,0,2], QQ (-1)), ([0,2,0], QQ (-2)), ([0,1,0], QQ 1), ([1,0,0], QQ 2)]
ex_2 = make_ordered_poly (lexi_order [3,2,1]) [([0,0,2], QQ 1), ([0,2,0], QQ (-1)), ([1,0,0], QQ 1)]
ex_3 = make_ordered_poly (lexi_order [3,2,1]) [([0,0,2], QQ (-1)), ([1,1,0], QQ 1)]

buchberger_algorithm [ex_1, ex_2, ex_3]
compute_reduced_groebner_basis [ex_1, ex_2, ex_3]

For example, we can use this to check that the order of the polynomials w.r.t. which which the reduction takes place matters. Defining

e = make_ordered_poly (lexi_order [1,2]) [([1,1], RR 1), ([0,1], RR 1)]
e_1 = make_ordered_poly (lexi_order [1,2]) [([1,0], RR 1), ([0,0], RR 1)]
e_2 = make_ordered_poly (lexi_order [1,2]) [([1,0], RR 1)]

and running

compute_normal_form [e_1,e_2] e
compute_normal_form [e_2,e_1] e

yields 0 and x₂, respectively.

We can also compute S-polynomials:

spol f_2 f_3