halg-polynomials-0.6.0.0: Polynomial rings and basic Gröbner basis computation, part of halg computational algebra suite.
Safe HaskellNone
LanguageHaskell2010

Algebra.Algorithms.Groebner

Synopsis

Groebner basis

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

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

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

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

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] Source #

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

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

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

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

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] Source #

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

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

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

reduceMinimalGroebnerBasis :: (Foldable t, Field (Coefficient poly), IsOrderedPolynomial poly) => t poly -> [poly] Source #

Reduce minimum Groebner basis into the reduced Groebner basis.

minimizeGroebnerBasis :: (Foldable t, Field (Coefficient poly), IsOrderedPolynomial poly) => t poly -> [poly] Source #

Minimises a Groebner basis

Selection Strategies

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

apply buchberger's algorithm using given selection strategy.

module Algebra.Algorithms.Groebner.SelectionStrategy

Ideal operations

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

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

intersection :: forall poly. (Field (Coefficient poly), IsOrderedPolynomial poly) => [Ideal poly] -> Ideal poly Source #

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) => SNat n -> Ideal poly -> Ideal (OrderedPolynomial (Coefficient poly) (MOrder poly) (Arity poly - n)) Source #

Calculate n-th elimination ideal using WeightedEliminationOrder ordering.

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

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, n <= m) => ord -> SNat n -> Ideal poly -> Ideal (OrderedPolynomial k Grevlex (m - n)) Source #

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.

eliminatePadding :: (IsOrderedPolynomial poly, IsMonomialOrder n ord, Field (Coefficient poly), SingI (Replicate n 1), KnownNat n) => Ideal (PadPolyL n ord poly) -> Ideal poly Source #

quotIdeal :: forall poly. (IsOrderedPolynomial poly, Field (Coefficient poly)) => Ideal poly -> Ideal poly -> Ideal poly Source #

Ideal quotient by the given ideal.

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

Ideal quotient by a principal ideals.

saturationIdeal :: forall poly. (Field (Coefficient poly), IsOrderedPolynomial poly) => Ideal poly -> Ideal poly -> Ideal poly Source #

Saturation ideal

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

Saturation by a principal ideal.

Resultant

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

Calculate resultant for given two unary polynomimals.

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

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

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

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

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

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