Safe Haskell	None
Language	Haskell98

Math.CommutativeAlgebra.GroebnerBasis

Description

A module providing an efficient implementation of the Buchberger algorithm for calculating the (reduced) Groebner basis for an ideal, together with some straightforward applications.

Synopsis

sPoly :: (Eq b3, Ord b, Algebra b3 b, Fractional b3, Monomial b) => Vect b3 b -> Vect b3 b -> Vect b3 b
isGB :: (Eq b3, Fractional b3, Monomial b, Ord b, Algebra b3 b) => [Vect b3 b] -> Bool
gb1 :: (Fractional b3, Monomial b, Ord b, Algebra b3 b, Eq b3) => [Vect b3 b] -> [Vect b3 b]
pairWith :: (a1 -> a1 -> a2) -> [a1] -> [a2]
reduce :: (Fractional k, Monomial b, Ord k, Ord b, Algebra k b) => [Vect k b] -> [Vect k b]
gb2 :: (Fractional k, Monomial b, Ord k, Ord b, Algebra k b) => [Vect k b] -> [Vect k b]
(!) :: [a] -> Int -> a
gb2a :: (Fractional k, Monomial b, Ord k, Ord b, Algebra k b) => [Vect k b] -> [Vect k b]
gb3 :: (Fractional k, Monomial b, Ord k, Ord b, Algebra k b) => [Vect k b] -> [Vect k b]
gb4 :: (Fractional k, Monomial b, Ord b, Ord k, Algebra k b) => [Vect k b] -> [Vect k b]
mergeBy :: (a -> a -> Ordering) -> [a] -> [a] -> [a]
gb :: (Fractional k, Ord k, Monomial m, Ord m, Algebra k m) => [Vect k m] -> [Vect k m]
sugar :: (Monomial m1, Monomial m2, Monomial m3) => Vect b1 m2 -> Vect b2 m3 -> m1 -> Int
cmpNormal :: (Ord a1, Ord b) => ((a2, a1), (a3, b)) -> ((a4, a1), (a5, b)) -> Ordering
cmpSug :: (Ord a1, Ord b, Ord c, Num a1) => ((a1, b), (a2, c)) -> ((a1, b), (a3, c)) -> Ordering
memberGB :: (Eq k, Fractional k, Monomial m, Ord m, Algebra k m) => Vect k m -> [Vect k m] -> Bool
memberI :: (Fractional k, Ord k, Monomial m, Ord m, Algebra k m) => Vect k m -> [Vect k m] -> Bool
sumI :: (Fractional k, Ord k, Monomial m, Ord m, Algebra k m) => [Vect k m] -> [Vect k m] -> [Vect k m]
productI :: (Fractional k, Ord k, Monomial m, Ord m, Algebra k m) => [Vect k m] -> [Vect k m] -> [Vect k m]
intersectI :: (Fractional k, Ord k, Monomial m, Ord m) => [Vect k m] -> [Vect k m] -> [Vect k m]
toElimFst :: (Functor f, Mon b) => f a -> f (Elim2 a b)
toElimSnd :: (Functor f, Mon a) => f b -> f (Elim2 a b)
isElimFst :: (Eq a, Mon a) => Vect b1 (Elim2 a b2) -> Bool
fromElimSnd :: Functor f => f (Elim2 a b) -> f b
eliminateFst :: (Fractional b1, Monomial a, Monomial b2, Ord b1, Ord a, Ord b2) => [Vect b1 (Elim2 a b2)] -> [Vect b1 b2]
quotientI :: (Fractional k, Ord k, Monomial m, Ord m, Algebra k m) => [Vect k m] -> [Vect k m] -> [Vect k m]
quotientP :: (Monomial m, Fractional k, Algebra k m, Ord m, Ord k) => [Vect k m] -> Vect k m -> [Vect k m]
eliminate :: (Eq k, Fractional k, Ord k, MonomialConstructor m, Monomial (m v), Ord (m v)) => [Vect k (m v)] -> [Vect k (m v)] -> [Vect k (m v)]
mbasis :: (Ord a, Num a) => [a] -> [a]
mbasisQA :: (Fractional k, Ord k, Monomial m, Ord m, Algebra k m) => [Vect k m] -> [Vect k m] -> [Vect k m]
ltIdeal :: (Fractional k, Ord k, Monomial m, Ord m, Algebra k m) => [Vect k m] -> [Vect k m]
numMonomials :: Integral a => a -> a -> Integer
hilbertFunQA :: (Fractional k, Ord k, Monomial m, Ord m, Algebra k m) => [Vect k m] -> [Vect k m] -> Int -> Integer
hilbertSeriesQA1 :: (Ord k, Fractional k, Monomial m, Ord m, Algebra k m) => [Vect k m] -> [Vect k m] -> [Int]
hilbertSeriesQA :: (Fractional k, Ord k, Monomial m, Ord m, Algebra k m) => [Vect k m] -> [Vect k m] -> [Integer]
hilbertSeriesQA' :: (Fractional k, Ord k, MonomialConstructor m, Ord (m v), Monomial (m v), Algebra k (m v)) => [Vect k (m v)] -> [Integer]
hilbertPolyQA :: (Fractional k, Ord k, Monomial m, Ord m, Algebra k m) => [Vect k m] -> [Vect k m] -> GlexPoly Q String
hilbertPolyQA' :: (Fractional k, Ord k, MonomialConstructor m, Ord (m v), Monomial (m v), Algebra k (m v)) => [Vect k (m v)] -> GlexPoly Q String
dim :: (Fractional k, Monomial m, Ord k, Ord m, Algebra k m) => [Vect k m] -> [Vect k m] -> Int
dim' :: (Fractional k, MonomialConstructor m, Ord k, Ord (m v), Monomial (m v), Algebra k (m v)) => [Vect k (m v)] -> Int

Documentation

sPoly :: (Eq b3, Ord b, Algebra b3 b, Fractional b3, Monomial b) => Vect b3 b -> Vect b3 b -> Vect b3 b Source #

isGB :: (Eq b3, Fractional b3, Monomial b, Ord b, Algebra b3 b) => [Vect b3 b] -> Bool Source #

gb1 :: (Fractional b3, Monomial b, Ord b, Algebra b3 b, Eq b3) => [Vect b3 b] -> [Vect b3 b] Source #

pairWith :: (a1 -> a1 -> a2) -> [a1] -> [a2] Source #

reduce :: (Fractional k, Monomial b, Ord k, Ord b, Algebra k b) => [Vect k b] -> [Vect k b] Source #

gb2 :: (Fractional k, Monomial b, Ord k, Ord b, Algebra k b) => [Vect k b] -> [Vect k b] Source #

(!) :: [a] -> Int -> a Source #

gb2a :: (Fractional k, Monomial b, Ord k, Ord b, Algebra k b) => [Vect k b] -> [Vect k b] Source #

gb3 :: (Fractional k, Monomial b, Ord k, Ord b, Algebra k b) => [Vect k b] -> [Vect k b] Source #

gb4 :: (Fractional k, Monomial b, Ord b, Ord k, Algebra k b) => [Vect k b] -> [Vect k b] Source #

mergeBy :: (a -> a -> Ordering) -> [a] -> [a] -> [a] Source #

gb :: (Fractional k, Ord k, Monomial m, Ord m, Algebra k m) => [Vect k m] -> [Vect k m] Source #

Given a list of polynomials over a field, return a Groebner basis for the ideal generated by the polynomials.

sugar :: (Monomial m1, Monomial m2, Monomial m3) => Vect b1 m2 -> Vect b2 m3 -> m1 -> Int Source #

cmpNormal :: (Ord a1, Ord b) => ((a2, a1), (a3, b)) -> ((a4, a1), (a5, b)) -> Ordering Source #

cmpSug :: (Ord a1, Ord b, Ord c, Num a1) => ((a1, b), (a2, c)) -> ((a1, b), (a3, c)) -> Ordering Source #

memberGB :: (Eq k, Fractional k, Monomial m, Ord m, Algebra k m) => Vect k m -> [Vect k m] -> Bool Source #

memberI :: (Fractional k, Ord k, Monomial m, Ord m, Algebra k m) => Vect k m -> [Vect k m] -> Bool Source #

memberI f gs returns whether f is in the ideal generated by gs

sumI :: (Fractional k, Ord k, Monomial m, Ord m, Algebra k m) => [Vect k m] -> [Vect k m] -> [Vect k m] Source #

Given ideals I and J, their sum is defined as I+J = {f+g | f <- I, g <- J}.

If fs and gs are generators for I and J, then sumI fs gs returns generators for I+J.

The geometric interpretation is that the variety of the sum is the intersection of the varieties, ie V(I+J) = V(I) intersect V(J)

productI :: (Fractional k, Ord k, Monomial m, Ord m, Algebra k m) => [Vect k m] -> [Vect k m] -> [Vect k m] Source #

Given ideals I and J, their product I.J is the ideal generated by all products {f.g | f <- I, g <- J}.

If fs and gs are generators for I and J, then productI fs gs returns generators for I.J.

The geometric interpretation is that the variety of the product is the union of the varieties, ie V(I.J) = V(I) union V(J)

intersectI :: (Fractional k, Ord k, Monomial m, Ord m) => [Vect k m] -> [Vect k m] -> [Vect k m] Source #

The intersection of ideals I and J is the set of all polynomials which belong to both I and J.

If fs and gs are generators for I and J, then intersectI fs gs returns generators for the intersection of I and J

The geometric interpretation is that the variety of the intersection is the union of the varieties, ie V(I intersect J) = V(I) union V(J).

The reason for prefering the intersection over the product is that the intersection of radical ideals is radical, whereas the product need not be.

toElimFst :: (Functor f, Mon b) => f a -> f (Elim2 a b) Source #

toElimSnd :: (Functor f, Mon a) => f b -> f (Elim2 a b) Source #

isElimFst :: (Eq a, Mon a) => Vect b1 (Elim2 a b2) -> Bool Source #

fromElimSnd :: Functor f => f (Elim2 a b) -> f b Source #

eliminateFst :: (Fractional b1, Monomial a, Monomial b2, Ord b1, Ord a, Ord b2) => [Vect b1 (Elim2 a b2)] -> [Vect b1 b2] Source #

quotientI :: (Fractional k, Ord k, Monomial m, Ord m, Algebra k m) => [Vect k m] -> [Vect k m] -> [Vect k m] Source #

Given ideals I and J, their quotient is defined as I:J = {f | f <- R, f.g is in I for all g in J}.

If fs and gs are generators for I and J, then quotientI fs gs returns generators for I:J.

The ideal quotient is the algebraic analogue of the Zariski closure of a difference of varieties. V(I:J) contains the Zariski closure of V(I)-V(J), with equality if k is algebraically closed and I is a radical ideal.

quotientP :: (Monomial m, Fractional k, Algebra k m, Ord m, Ord k) => [Vect k m] -> Vect k m -> [Vect k m] Source #

eliminate :: (Eq k, Fractional k, Ord k, MonomialConstructor m, Monomial (m v), Ord (m v)) => [Vect k (m v)] -> [Vect k (m v)] -> [Vect k (m v)] Source #

eliminate vs gs returns the elimination ideal obtained from the ideal generated by gs by eliminating the variables vs.

mbasis :: (Ord a, Num a) => [a] -> [a] Source #

mbasisQA :: (Fractional k, Ord k, Monomial m, Ord m, Algebra k m) => [Vect k m] -> [Vect k m] -> [Vect k m] Source #

Given variables vs, and a Groebner basis gs, mbasisQA vs gs returns a monomial basis for the quotient algebra k[vs]/<gs>. For example, mbasisQA [x,y] [x^2+y^2-1] returns a monomial basis for k[x,y]/<x^2+y^2-1>. In general, the monomial basis is likely to be infinite.

ltIdeal :: (Fractional k, Ord k, Monomial m, Ord m, Algebra k m) => [Vect k m] -> [Vect k m] Source #

Given an ideal I, the leading term ideal lt(I) consists of the leading terms of all elements of I. If I is generated by gs, then ltIdeal gs returns generators for lt(I).

numMonomials :: Integral a => a -> a -> Integer Source #

hilbertFunQA :: (Fractional k, Ord k, Monomial m, Ord m, Algebra k m) => [Vect k m] -> [Vect k m] -> Int -> Integer Source #

Given variables vs, and a homogeneous ideal gs, hilbertFunQA vs gs returns the Hilbert function for the quotient algebra k[vs]/<gs>. Given an integer i, the Hilbert function returns the number of degree i monomials in a basis for k[vs]/<gs>. For a homogeneous ideal, this number is independent of the monomial ordering used (even though the elements of the monomial basis themselves are dependent on the ordering).

If the ideal I is not homogeneous, then R/I is not graded, and the Hilbert function is not well-defined. Specifically, the number of degree i monomials in a basis is likely to depend on which monomial ordering you use.

hilbertSeriesQA1 :: (Ord k, Fractional k, Monomial m, Ord m, Algebra k m) => [Vect k m] -> [Vect k m] -> [Int] Source #

hilbertSeriesQA :: (Fractional k, Ord k, Monomial m, Ord m, Algebra k m) => [Vect k m] -> [Vect k m] -> [Integer] Source #

Given variables vs, and a homogeneous ideal gs, hilbertSeriesQA vs gs returns the Hilbert series for the quotient algebra k[vs]/<gs>. The Hilbert series should be interpreted as a formal power series where the coefficient of t^i is the Hilbert function evaluated at i. That is, the i'th element in the series is the number of degree i monomials in a basis for k[vs]/<gs>.

hilbertSeriesQA' :: (Fractional k, Ord k, MonomialConstructor m, Ord (m v), Monomial (m v), Algebra k (m v)) => [Vect k (m v)] -> [Integer] Source #

In the case where every variable v occurs in some generator g of the homogeneous ideal (the usual case), then the vs can be inferred from the gs. hilbertSeriesQA' gs returns the Hilbert series for the quotient algebra k[vs]/<gs>.

hilbertPolyQA :: (Fractional k, Ord k, Monomial m, Ord m, Algebra k m) => [Vect k m] -> [Vect k m] -> GlexPoly Q String Source #

For i >> 0, the Hilbert function becomes a polynomial in i, called the Hilbert polynomial.

hilbertPolyQA' :: (Fractional k, Ord k, MonomialConstructor m, Ord (m v), Monomial (m v), Algebra k (m v)) => [Vect k (m v)] -> GlexPoly Q String Source #

dim :: (Fractional k, Monomial m, Ord k, Ord m, Algebra k m) => [Vect k m] -> [Vect k m] -> Int Source #

dim' :: (Fractional k, MonomialConstructor m, Ord k, Ord (m v), Monomial (m v), Algebra k (m v)) => [Vect k (m v)] -> Int Source #