| Safe Haskell | None |
|---|
Algebra.Algorithms.Groebner
- divModPolynomial :: (IsMonomialOrder order, IsPolynomial r n, Field r) => OrderedPolynomial r order n -> [OrderedPolynomial r order n] -> ([(OrderedPolynomial r order n, OrderedPolynomial r order n)], OrderedPolynomial r order n)
- divPolynomial :: (IsPolynomial r n, Field r, IsMonomialOrder order) => OrderedPolynomial r order n -> [OrderedPolynomial r order n] -> [(OrderedPolynomial r order n, OrderedPolynomial r order n)]
- modPolynomial :: (IsPolynomial r n, Field r, IsMonomialOrder order) => OrderedPolynomial r order n -> [OrderedPolynomial r order n] -> OrderedPolynomial r order n
- calcGroebnerBasis :: (Field k, IsPolynomial k n, IsMonomialOrder order) => Ideal (OrderedPolynomial k order n) -> [OrderedPolynomial k order n]
- calcGroebnerBasisWith :: (Field k, IsPolynomial k n, IsMonomialOrder order, IsMonomialOrder order') => order -> Ideal (OrderedPolynomial k order' n) -> [OrderedPolynomial k order n]
- calcGroebnerBasisWithStrategy :: (Field k, IsPolynomial k n, IsMonomialOrder order, SelectionStrategy strategy, Ord (Weight strategy order)) => strategy -> Ideal (OrderedPolynomial k order n) -> [OrderedPolynomial k order n]
- buchberger :: (Field r, IsPolynomial r n, IsMonomialOrder order) => Ideal (OrderedPolynomial r order n) -> [OrderedPolynomial r order n]
- syzygyBuchberger :: (Field r, IsPolynomial r n, IsMonomialOrder order) => Ideal (OrderedPolynomial r order n) -> [OrderedPolynomial r order n]
- simpleBuchberger :: (Field k, IsPolynomial k n, IsMonomialOrder order) => Ideal (OrderedPolynomial k order n) -> [OrderedPolynomial k order n]
- primeTestBuchberger :: (Field r, IsPolynomial r n, IsMonomialOrder order) => Ideal (OrderedPolynomial r order n) -> [OrderedPolynomial r order n]
- reduceMinimalGroebnerBasis :: (Field k, IsPolynomial k n, IsMonomialOrder order) => [OrderedPolynomial k order n] -> [OrderedPolynomial k order n]
- minimizeGroebnerBasis :: (Field k, IsPolynomial k n, IsMonomialOrder order) => [OrderedPolynomial k order n] -> [OrderedPolynomial k order n]
- syzygyBuchbergerWithStrategy :: (Field r, IsPolynomial r n, IsMonomialOrder order, SelectionStrategy strategy, Ord (Weight strategy order)) => strategy -> Ideal (OrderedPolynomial r order n) -> [OrderedPolynomial r order n]
- class SelectionStrategy s where
- type Weight s ord :: *
- calcWeight :: (IsPolynomial r n, IsMonomialOrder ord) => Proxy s -> OrderedPolynomial r ord n -> OrderedPolynomial r ord n -> Weight s ord
- calcWeight' :: (SelectionStrategy s, IsPolynomial r n, IsMonomialOrder ord, Ord (Weight s ord)) => s -> OrderedPolynomial r ord n -> OrderedPolynomial r ord n -> Weight s ord
- data GrevlexStrategy = GrevlexStrategy
- data NormalStrategy = NormalStrategy
- data SugarStrategy s = SugarStrategy s
- data GradedStrategy = GradedStrategy
- isIdealMember :: (IsPolynomial k n, Field k, IsMonomialOrder o) => OrderedPolynomial k o n -> Ideal (OrderedPolynomial k o n) -> Bool
- intersection :: forall r k n ord. (IsMonomialOrder ord, Field r, IsPolynomial r k, IsPolynomial r n, IsPolynomial r (k :+: n)) => Vector (Ideal (OrderedPolynomial r ord n)) k -> Ideal (OrderedPolynomial r ord n)
- thEliminationIdeal :: (IsMonomialOrder ord, Field k, IsPolynomial k m, IsPolynomial k (m :-: n), (n :<<= m) ~ True) => SNat n -> Ideal (OrderedPolynomial k ord m) -> Ideal (OrderedPolynomial k ord (m :-: n))
- thEliminationIdealWith :: (IsMonomialOrder ord, Field k, IsPolynomial k m, IsPolynomial k (m :-: n), (n :<<= m) ~ True, EliminationType n ord, IsMonomialOrder ord') => ord -> SNat n -> Ideal (OrderedPolynomial k ord' m) -> Ideal (OrderedPolynomial k ord (m :-: n))
- unsafeThEliminationIdealWith :: (IsMonomialOrder ord, Field k, IsPolynomial k m, IsPolynomial k (m :-: n), (n :<<= m) ~ True, IsMonomialOrder ord') => ord -> SNat n -> Ideal (OrderedPolynomial k ord' m) -> Ideal (OrderedPolynomial k ord (m :-: n))
- quotIdeal :: forall k ord n. (IsPolynomial k n, Field k, IsMonomialOrder ord) => Ideal (OrderedPolynomial k ord n) -> Ideal (OrderedPolynomial k ord n) -> Ideal (OrderedPolynomial k ord n)
- quotByPrincipalIdeal :: (Field k, IsPolynomial k n, IsMonomialOrder ord) => Ideal (OrderedPolynomial k ord n) -> OrderedPolynomial k ord n -> Ideal (OrderedPolynomial k ord n)
- saturationIdeal :: forall k ord n. (IsPolynomial k n, Field k, IsMonomialOrder ord) => Ideal (OrderedPolynomial k ord n) -> Ideal (OrderedPolynomial k ord n) -> Ideal (OrderedPolynomial k ord n)
- saturationByPrincipalIdeal :: (Field k, IsPolynomial k n, IsMonomialOrder ord) => Ideal (OrderedPolynomial k ord n) -> OrderedPolynomial k ord n -> Ideal (OrderedPolynomial k ord n)
- resultant :: forall k ord. (Eq k, NoetherianRing k, Field k, IsMonomialOrder ord) => OrderedPolynomial k ord One -> OrderedPolynomial k ord One -> k
- hasCommonFactor :: forall k ord. (NoetherianRing k, Eq k, Field k, IsMonomialOrder ord) => OrderedPolynomial k ord One -> OrderedPolynomial k ord One -> Bool
Polynomial division
divModPolynomial :: (IsMonomialOrder order, IsPolynomial r n, Field r) => OrderedPolynomial r order n -> [OrderedPolynomial r order n] -> ([(OrderedPolynomial r order n, OrderedPolynomial r order n)], OrderedPolynomial r order n)Source
Calculate a polynomial quotient and remainder w.r.t. second argument.
divPolynomial :: (IsPolynomial r n, Field r, IsMonomialOrder order) => OrderedPolynomial r order n -> [OrderedPolynomial r order n] -> [(OrderedPolynomial r order n, OrderedPolynomial r order n)]Source
A Quotient of given polynomial w.r.t. the second argument.
modPolynomial :: (IsPolynomial r n, Field r, IsMonomialOrder order) => OrderedPolynomial r order n -> [OrderedPolynomial r order n] -> OrderedPolynomial r order nSource
Remainder of given polynomial w.r.t. the second argument.
Groebner basis
calcGroebnerBasis :: (Field k, IsPolynomial k n, IsMonomialOrder order) => Ideal (OrderedPolynomial k order n) -> [OrderedPolynomial k order n]Source
Caliculating reduced Groebner basis of the given ideal.
calcGroebnerBasisWith :: (Field k, IsPolynomial k n, IsMonomialOrder order, IsMonomialOrder order') => order -> Ideal (OrderedPolynomial k order' n) -> [OrderedPolynomial k order n]Source
Caliculating reduced Groebner basis of the given ideal w.r.t. the specified monomial order.
calcGroebnerBasisWithStrategy :: (Field k, IsPolynomial k n, IsMonomialOrder order, SelectionStrategy strategy, Ord (Weight strategy order)) => strategy -> Ideal (OrderedPolynomial k order n) -> [OrderedPolynomial k order n]Source
Caliculating reduced Groebner basis of the given ideal w.r.t. the specified monomial order.
buchberger :: (Field r, IsPolynomial r n, IsMonomialOrder order) => Ideal (OrderedPolynomial r order n) -> [OrderedPolynomial r order n]Source
Calculate Groebner basis applying (modified) Buchberger's algorithm.
This function is same as syzygyBuchberger.
syzygyBuchberger :: (Field r, IsPolynomial r n, IsMonomialOrder order) => Ideal (OrderedPolynomial r order n) -> [OrderedPolynomial r order n]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 k, IsPolynomial k n, IsMonomialOrder order) => Ideal (OrderedPolynomial k order n) -> [OrderedPolynomial k order n]Source
The Naive buchberger's algorithm to calculate Groebner basis for the given ideal.
primeTestBuchberger :: (Field r, IsPolynomial r n, IsMonomialOrder order) => Ideal (OrderedPolynomial r order n) -> [OrderedPolynomial r order n]Source
Buchberger's algorithm slightly improved by discarding relatively prime pair.
reduceMinimalGroebnerBasis :: (Field k, IsPolynomial k n, IsMonomialOrder order) => [OrderedPolynomial k order n] -> [OrderedPolynomial k order n]Source
Reduce minimum Groebner basis into reduced Groebner basis.
minimizeGroebnerBasis :: (Field k, IsPolynomial k n, IsMonomialOrder order) => [OrderedPolynomial k order n] -> [OrderedPolynomial k order n]Source
Selection Strategies
syzygyBuchbergerWithStrategy :: (Field r, IsPolynomial r n, IsMonomialOrder order, SelectionStrategy strategy, Ord (Weight strategy order)) => strategy -> Ideal (OrderedPolynomial r order n) -> [OrderedPolynomial r order n]Source
apply buchberger's algorithm using given selection strategy.
class SelectionStrategy s whereSource
Type-class for selection strategies in Buchberger's algorithm.
Methods
calcWeight :: (IsPolynomial r n, IsMonomialOrder ord) => Proxy s -> OrderedPolynomial r ord n -> OrderedPolynomial r ord n -> Weight s ordSource
Instances
| SelectionStrategy GradedStrategy | Choose the pair with the least LCM(LT(f), LT(g)) w.r.t. graded current ordering. |
| SelectionStrategy GrevlexStrategy | |
| SelectionStrategy NormalStrategy | |
| SelectionStrategy s => SelectionStrategy (SugarStrategy s) |
calcWeight' :: (SelectionStrategy s, IsPolynomial r n, IsMonomialOrder ord, Ord (Weight s ord)) => s -> OrderedPolynomial r ord n -> OrderedPolynomial r ord n -> Weight s ordSource
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 Source
Choose the pair with the least LCM(LT(f), LT(g)) w.r.t. Grevlex order.
Constructors
| GrevlexStrategy |
data NormalStrategy Source
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 |
data SugarStrategy s Source
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) | |
| Ord s => Ord (SugarStrategy s) | |
| Read s => Read (SugarStrategy s) | |
| Show s => Show (SugarStrategy s) | |
| SelectionStrategy s => SelectionStrategy (SugarStrategy s) |
data GradedStrategy Source
Constructors
| GradedStrategy |
Instances
| Eq GradedStrategy | |
| Ord GradedStrategy | |
| Read GradedStrategy | |
| Show GradedStrategy | |
| SelectionStrategy GradedStrategy | Choose the pair with the least LCM(LT(f), LT(g)) w.r.t. graded current ordering. |
Ideal operations
isIdealMember :: (IsPolynomial k n, Field k, IsMonomialOrder o) => OrderedPolynomial k o n -> Ideal (OrderedPolynomial k o n) -> BoolSource
Test if the given polynomial is the member of the ideal.
intersection :: forall r k n ord. (IsMonomialOrder ord, Field r, IsPolynomial r k, IsPolynomial r n, IsPolynomial r (k :+: n)) => Vector (Ideal (OrderedPolynomial r ord n)) k -> Ideal (OrderedPolynomial r ord n)Source
An intersection ideal of given ideals (using WeightedEliminationOrder).
thEliminationIdeal :: (IsMonomialOrder ord, Field k, IsPolynomial k m, IsPolynomial k (m :-: n), (n :<<= m) ~ True) => SNat n -> Ideal (OrderedPolynomial k ord m) -> Ideal (OrderedPolynomial k ord (m :-: n))Source
Calculate n-th elimination ideal using WeightedEliminationOrder ordering.
thEliminationIdealWith :: (IsMonomialOrder ord, Field k, IsPolynomial k m, IsPolynomial k (m :-: n), (n :<<= m) ~ True, EliminationType n ord, IsMonomialOrder ord') => ord -> SNat n -> Ideal (OrderedPolynomial k ord' m) -> Ideal (OrderedPolynomial k ord (m :-: n))Source
Calculate n-th elimination ideal using the specified n-th elimination type order.
unsafeThEliminationIdealWith :: (IsMonomialOrder ord, Field k, IsPolynomial k m, IsPolynomial k (m :-: n), (n :<<= m) ~ True, IsMonomialOrder ord') => ord -> SNat n -> Ideal (OrderedPolynomial k ord' m) -> Ideal (OrderedPolynomial k ord (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.
quotIdeal :: forall k ord n. (IsPolynomial k n, Field k, IsMonomialOrder ord) => Ideal (OrderedPolynomial k ord n) -> Ideal (OrderedPolynomial k ord n) -> Ideal (OrderedPolynomial k ord n)Source
Ideal quotient by the given ideal.
quotByPrincipalIdeal :: (Field k, IsPolynomial k n, IsMonomialOrder ord) => Ideal (OrderedPolynomial k ord n) -> OrderedPolynomial k ord n -> Ideal (OrderedPolynomial k ord n)Source
Ideal quotient by a principal ideals.
saturationIdeal :: forall k ord n. (IsPolynomial k n, Field k, IsMonomialOrder ord) => Ideal (OrderedPolynomial k ord n) -> Ideal (OrderedPolynomial k ord n) -> Ideal (OrderedPolynomial k ord n)Source
Saturation ideal
saturationByPrincipalIdeal :: (Field k, IsPolynomial k n, IsMonomialOrder ord) => Ideal (OrderedPolynomial k ord n) -> OrderedPolynomial k ord n -> Ideal (OrderedPolynomial k ord n)Source
Saturation by a principal ideal.
Resultant
resultant :: forall k ord. (Eq k, NoetherianRing k, Field k, IsMonomialOrder ord) => OrderedPolynomial k ord One -> OrderedPolynomial k ord One -> kSource
Calculate resultant for given two unary polynomimals.
hasCommonFactor :: forall k ord. (NoetherianRing k, Eq k, Field k, IsMonomialOrder ord) => OrderedPolynomial k ord One -> OrderedPolynomial k ord One -> BoolSource