Algebra.Algorithms.Groebner

Groebner basis

isGroebnerBasis :: (IsOrderedPolynomial poly, Field (Coefficient poly)) => Ideal poly -> Bool

Test if the given ideal is Groebner basis, using Buchberger criteria and relatively primeness.

calcGroebnerBasis :: (Field (Coefficient poly), IsOrderedPolynomial poly) => Ideal poly -> [poly]

Caliculating reduced Groebner basis of the given ideal.

calcGroebnerBasisWith :: (IsOrderedPolynomial poly, Field (Coefficient poly), IsMonomialOrder (Arity poly) order) => order -> Ideal poly -> [OrderedPolynomial (Coefficient poly) order (Arity poly)]

Caliculating reduced Groebner basis of the given ideal w.r.t. the specified monomial order.

calcGroebnerBasisWithStrategy :: (Field (Coefficient poly), IsOrderedPolynomial poly, SelectionStrategy (Arity poly) strategy, Ord (Weight (Arity poly) strategy (MOrder poly))) => strategy -> Ideal poly -> [poly]

Caliculating reduced Groebner basis of the given ideal w.r.t. the specified monomial order.

buchberger :: (Field (Coefficient poly), IsOrderedPolynomial poly) => Ideal poly -> [poly]

Calculate Groebner basis applying (modified) Buchberger's algorithm. This function is same as syzygyBuchberger.

syzygyBuchberger :: (Field (Coefficient poly), IsOrderedPolynomial poly) => Ideal poly -> [poly]

Buchberger's algorithm greately improved using the syzygy theory with the sugar strategy. Utilizing priority queues, this function reduces division complexity and comparison time. If you don't have strong reason to avoid this function, this function is recommended to use.

simpleBuchberger :: (Field (Coefficient poly), IsOrderedPolynomial poly) => Ideal poly -> [poly]

The Naive buchberger's algorithm to calculate Groebner basis for the given ideal.

primeTestBuchberger :: (Field (Coefficient poly), IsOrderedPolynomial poly) => Ideal poly -> [poly]

Buchberger's algorithm slightly improved by discarding relatively prime pair.

reduceMinimalGroebnerBasis :: (Field (Coefficient poly), IsOrderedPolynomial poly) => [poly] -> [poly]

Reduce minimum Groebner basis into reduced Groebner basis.

minimizeGroebnerBasis :: (Field (Coefficient poly), IsOrderedPolynomial poly) => [poly] -> [poly]

Selection Strategies

syzygyBuchbergerWithStrategy :: (Field (Coefficient poly), IsOrderedPolynomial poly, SelectionStrategy (Arity poly) strategy, Ord (Weight (Arity poly) strategy (MOrder poly))) => strategy -> Ideal poly -> [poly]

apply buchberger's algorithm using given selection strategy.

class SelectionStrategy n s where

Type-class for selection strategies in Buchberger's algorithm.

Minimal complete definition

calcWeight

Associated Types

type Weight n s ord :: *

Methods

calcWeight :: (IsOrderedPolynomial poly, n ~ Arity poly) => Proxy s -> poly -> poly -> Weight n s (MOrder poly)

Calculates the weight for the given pair of polynomial used for selection strategy.

Instances

SelectionStrategy * n GradedStrategy

Choose the pair with the least LCM(LT(f), LT(g)) w.r.t. graded current ordering.

Associated Types

type Weight n (GradedStrategy :: Nat) (s :: n) ord :: *

Methods

calcWeight :: (IsOrderedPolynomial poly, (Nat ~ GradedStrategy) (Arity poly)) => Proxy n s -> poly -> poly -> Weight n GradedStrategy s (MOrder poly)

SelectionStrategy * n GrevlexStrategy

Associated Types

type Weight n (GrevlexStrategy :: Nat) (s :: n) ord :: *

Methods

calcWeight :: (IsOrderedPolynomial poly, (Nat ~ GrevlexStrategy) (Arity poly)) => Proxy n s -> poly -> poly -> Weight n GrevlexStrategy s (MOrder poly)

SelectionStrategy * n NormalStrategy

Associated Types

type Weight n (NormalStrategy :: Nat) (s :: n) ord :: *

Methods

calcWeight :: (IsOrderedPolynomial poly, (Nat ~ NormalStrategy) (Arity poly)) => Proxy n s -> poly -> poly -> Weight n NormalStrategy s (MOrder poly)

SelectionStrategy * n s => SelectionStrategy * n (SugarStrategy s)

Associated Types

type Weight n (SugarStrategy s :: Nat) (s :: n) ord :: *

Methods

calcWeight :: (IsOrderedPolynomial poly, (Nat ~ SugarStrategy s) (Arity poly)) => Proxy n s -> poly -> poly -> Weight n (SugarStrategy s) s (MOrder poly)

calcWeight' :: (SelectionStrategy (Arity poly) s, IsOrderedPolynomial poly) => s -> poly -> poly -> Weight (Arity poly) s (MOrder poly)

Calculate the weight of given polynomials w.r.t. the given strategy. Buchberger's algorithm proccesses the pair with the most least weight first. This function requires the Ord instance for the weight; this constraint is not required in the calcWeight because of the ease of implementation. So use this function.

data GrevlexStrategy

Choose the pair with the least LCM(LT(f), LT(g)) w.r.t. Grevlex order.

Constructors

GrevlexStrategy

Instances

Eq GrevlexStrategy

Methods

(==) :: GrevlexStrategy -> GrevlexStrategy -> Bool

(/=) :: GrevlexStrategy -> GrevlexStrategy -> Bool

Ord GrevlexStrategy

Methods

compare :: GrevlexStrategy -> GrevlexStrategy -> Ordering

(<) :: GrevlexStrategy -> GrevlexStrategy -> Bool

(<=) :: GrevlexStrategy -> GrevlexStrategy -> Bool

(>) :: GrevlexStrategy -> GrevlexStrategy -> Bool

(>=) :: GrevlexStrategy -> GrevlexStrategy -> Bool

max :: GrevlexStrategy -> GrevlexStrategy -> GrevlexStrategy

min :: GrevlexStrategy -> GrevlexStrategy -> GrevlexStrategy

Read GrevlexStrategy

Methods

readsPrec :: Int -> ReadS GrevlexStrategy

readList :: ReadS [GrevlexStrategy]

readPrec :: ReadPrec GrevlexStrategy

readListPrec :: ReadPrec [GrevlexStrategy]

Show GrevlexStrategy

Methods

showsPrec :: Int -> GrevlexStrategy -> ShowS

show :: GrevlexStrategy -> String

showList :: [GrevlexStrategy] -> ShowS

SelectionStrategy * n GrevlexStrategy

Associated Types

type Weight n (GrevlexStrategy :: Nat) (s :: n) ord :: *

Methods

calcWeight :: (IsOrderedPolynomial poly, (Nat ~ GrevlexStrategy) (Arity poly)) => Proxy n s -> poly -> poly -> Weight n GrevlexStrategy s (MOrder poly)

type Weight * n GrevlexStrategy ord

type Weight * n GrevlexStrategy ord = OrderedMonomial * Grevlex n

data NormalStrategy

Buchberger's normal selection strategy. This selects the pair with the least LCM(LT(f), LT(g)) w.r.t. current monomial ordering.

Constructors

NormalStrategy

Instances

Eq NormalStrategy

Methods

(==) :: NormalStrategy -> NormalStrategy -> Bool

(/=) :: NormalStrategy -> NormalStrategy -> Bool

Ord NormalStrategy

Methods

compare :: NormalStrategy -> NormalStrategy -> Ordering

(<) :: NormalStrategy -> NormalStrategy -> Bool

(<=) :: NormalStrategy -> NormalStrategy -> Bool

(>) :: NormalStrategy -> NormalStrategy -> Bool

(>=) :: NormalStrategy -> NormalStrategy -> Bool

max :: NormalStrategy -> NormalStrategy -> NormalStrategy

min :: NormalStrategy -> NormalStrategy -> NormalStrategy

Read NormalStrategy

Methods

readsPrec :: Int -> ReadS NormalStrategy

readList :: ReadS [NormalStrategy]

readPrec :: ReadPrec NormalStrategy

readListPrec :: ReadPrec [NormalStrategy]

Show NormalStrategy

Methods

showsPrec :: Int -> NormalStrategy -> ShowS

show :: NormalStrategy -> String

showList :: [NormalStrategy] -> ShowS

SelectionStrategy * n NormalStrategy

Associated Types

type Weight n (NormalStrategy :: Nat) (s :: n) ord :: *

Methods

calcWeight :: (IsOrderedPolynomial poly, (Nat ~ NormalStrategy) (Arity poly)) => Proxy n s -> poly -> poly -> Weight n NormalStrategy s (MOrder poly)

type Weight * n NormalStrategy ord

type Weight * n NormalStrategy ord = OrderedMonomial * ord n

data SugarStrategy s

Sugar strategy. This chooses the pair with the least phantom homogenized degree and then break the tie with the given strategy (say s).

Constructors

SugarStrategy s

Instances

Eq s => Eq (SugarStrategy s)

Methods

(==) :: SugarStrategy s -> SugarStrategy s -> Bool

(/=) :: SugarStrategy s -> SugarStrategy s -> Bool

Ord s => Ord (SugarStrategy s)

Methods

compare :: SugarStrategy s -> SugarStrategy s -> Ordering

(<) :: SugarStrategy s -> SugarStrategy s -> Bool

(<=) :: SugarStrategy s -> SugarStrategy s -> Bool

(>) :: SugarStrategy s -> SugarStrategy s -> Bool

(>=) :: SugarStrategy s -> SugarStrategy s -> Bool

max :: SugarStrategy s -> SugarStrategy s -> SugarStrategy s

min :: SugarStrategy s -> SugarStrategy s -> SugarStrategy s

Read s => Read (SugarStrategy s)

Methods

readsPrec :: Int -> ReadS (SugarStrategy s)

readList :: ReadS [SugarStrategy s]

readPrec :: ReadPrec (SugarStrategy s)

readListPrec :: ReadPrec [SugarStrategy s]

Show s => Show (SugarStrategy s)

Methods

showsPrec :: Int -> SugarStrategy s -> ShowS

show :: SugarStrategy s -> String

showList :: [SugarStrategy s] -> ShowS

SelectionStrategy * n s => SelectionStrategy * n (SugarStrategy s)

Associated Types

type Weight n (SugarStrategy s :: Nat) (s :: n) ord :: *

Methods

calcWeight :: (IsOrderedPolynomial poly, (Nat ~ SugarStrategy s) (Arity poly)) => Proxy n s -> poly -> poly -> Weight n (SugarStrategy s) s (MOrder poly)

type Weight * n (SugarStrategy s) ord

type Weight * n (SugarStrategy s) ord = (Int, Weight * n s ord)

data GradedStrategy

Constructors

GradedStrategy

Instances

Eq GradedStrategy

Methods

(==) :: GradedStrategy -> GradedStrategy -> Bool

(/=) :: GradedStrategy -> GradedStrategy -> Bool

Ord GradedStrategy

Methods

compare :: GradedStrategy -> GradedStrategy -> Ordering

(<) :: GradedStrategy -> GradedStrategy -> Bool

(<=) :: GradedStrategy -> GradedStrategy -> Bool

(>) :: GradedStrategy -> GradedStrategy -> Bool

(>=) :: GradedStrategy -> GradedStrategy -> Bool

max :: GradedStrategy -> GradedStrategy -> GradedStrategy

min :: GradedStrategy -> GradedStrategy -> GradedStrategy

Read GradedStrategy

Methods

readsPrec :: Int -> ReadS GradedStrategy

readList :: ReadS [GradedStrategy]

readPrec :: ReadPrec GradedStrategy

readListPrec :: ReadPrec [GradedStrategy]

Show GradedStrategy

Methods

showsPrec :: Int -> GradedStrategy -> ShowS

show :: GradedStrategy -> String

showList :: [GradedStrategy] -> ShowS

SelectionStrategy * n GradedStrategy

Choose the pair with the least LCM(LT(f), LT(g)) w.r.t. graded current ordering.

Associated Types

type Weight n (GradedStrategy :: Nat) (s :: n) ord :: *

Methods

calcWeight :: (IsOrderedPolynomial poly, (Nat ~ GradedStrategy) (Arity poly)) => Proxy n s -> poly -> poly -> Weight n GradedStrategy s (MOrder poly)

type Weight * n GradedStrategy ord

type Weight * n GradedStrategy ord = OrderedMonomial * (Graded ord) n

Ideal operations

isIdealMember :: (Field (Coefficient poly), IsOrderedPolynomial poly) => poly -> Ideal poly -> Bool

Test if the given polynomial is the member of the ideal.

intersection :: forall poly k. (Field (Coefficient poly), IsOrderedPolynomial poly) => Sized k (Ideal poly) -> Ideal poly

An intersection ideal of given ideals (using WeightedEliminationOrder).

thEliminationIdeal :: forall poly n. (IsMonomialOrder (Arity poly - n) (MOrder poly), Field (Coefficient poly), IsOrderedPolynomial poly, (n :<= Arity poly) ~ True) => SNat n -> Ideal poly -> Ideal (OrderedPolynomial (Coefficient poly) (MOrder poly) (Arity poly :-. n))

Calculate n-th elimination ideal using WeightedEliminationOrder ordering.

thEliminationIdealWith :: (IsOrderedPolynomial poly, m ~ Arity poly, k ~ Coefficient poly, Field k, KnownNat (m :-. n), (n :<= m) ~ True, EliminationType m n ord) => ord -> SNat n -> Ideal poly -> Ideal (OrderedPolynomial k Grevlex (m :-. n))

Calculate n-th elimination ideal using the specified n-th elimination type order.

unsafeThEliminationIdealWith :: (IsOrderedPolynomial poly, m ~ Arity poly, k ~ Coefficient poly, Field k, IsMonomialOrder m ord, KnownNat (m :-. n), (n :<= m) ~ True) => ord -> SNat n -> Ideal poly -> Ideal (OrderedPolynomial k Grevlex (m :-. n))

Calculate n-th elimination ideal using the specified n-th elimination type order. This function should be used carefully because it does not check whether the given ordering is n-th elimintion type or not.

quotIdeal :: forall poly l. (IsOrderedPolynomial poly, Field (Coefficient poly)) => Ideal poly -> Sized l poly -> Ideal poly

Ideal quotient by the given ideal.

quotByPrincipalIdeal :: (Field (Coefficient poly), IsOrderedPolynomial poly) => Ideal poly -> poly -> Ideal poly

Ideal quotient by a principal ideals.

saturationIdeal :: forall poly l. (Field (Coefficient poly), IsOrderedPolynomial poly) => Ideal poly -> Sized l poly -> Ideal poly

Saturation ideal

saturationByPrincipalIdeal :: forall poly. (IsOrderedPolynomial poly, Field (Coefficient poly)) => Ideal poly -> poly -> Ideal poly

Saturation by a principal ideal.

Resultant

resultant :: forall poly. (Field (Coefficient poly), IsOrderedPolynomial poly, Arity poly ~ 1) => poly -> poly -> Coefficient poly

Calculate resultant for given two unary polynomimals.

hasCommonFactor :: (Field (Coefficient poly), IsOrderedPolynomial poly, Arity poly ~ 1) => poly -> poly -> Bool

Determine whether two polynomials have a common factor with positive degree using resultant.

lcmPolynomial :: forall poly. (Field (Coefficient poly), IsOrderedPolynomial poly) => poly -> poly -> poly

Calculates the Least Common Multiply of the given pair of polynomials.

gcdPolynomial :: (Field (Coefficient poly), IsOrderedPolynomial poly) => poly -> poly -> poly

Calculates the Greatest Common Divisor of the given pair of polynomials.