Algebra.Ring.Polynomial

Documentation

type Polynomial r = OrderedPolynomial r Grevlex

type Monomial n = Vector Int n

N-ary Monomial. IntMap contains degrees for each x_i.

type MonomialOrder = forall n. Monomial n -> Monomial n -> Ordering

Monomial order (of degree n). This should satisfy following laws: (1) Totality: forall a, b (a < b || a == b || b < a) (2) Additivity: a b == a + c <= b + c (3) Non-negative: forall a, 0 <= a

class (IsMonomialOrder ord, SingRep n) => EliminationType n ord

Monomial order which can be use to calculate n-th elimination ideal. This should judge it as bigger that contains variables to eliminate.

Instances

SingRep k n => EliminationType k n Lex

(SingRep Nat n, IsMonomialOrder ord) => EliminationType Nat n (WeightedEliminationOrder n ord)

IsMonomialOrder ord => EliminationType Nat Z (WeightOrder ([] Nat) ord)

(SingRep Nat n, IsMonomialOrder ord, IsMonomialOrder ord') => EliminationType Nat n (ProductOrder n ord ord')

(IsMonomialOrder ord, ToWeightVector ns, EliminationType Nat n (WeightOrder ns ord)) => EliminationType Nat (S n) (WeightOrder (: Nat One ns) ord)

type EliminationOrder n = ProductOrder n Grevlex Grevlex

data WeightedEliminationOrder n ord

Instances

(SingRep Nat n, IsMonomialOrder ord) => EliminationType Nat n (WeightedEliminationOrder n ord)

(SingRep Nat n, IsMonomialOrder ord) => IsMonomialOrder (WeightedEliminationOrder n ord)

(SingRep Nat n, IsMonomialOrder ord) => IsOrder (WeightedEliminationOrder n ord)

eliminationOrder :: SNat n -> EliminationOrder n

weightedEliminationOrder :: SNat n -> WeightedEliminationOrder n Grevlex

lex :: MonomialOrder

Lexicographical order. This *is* a monomial order.

revlex :: Monomial n -> Monomial n -> Ordering

Reversed lexicographical order. This is *not* a monomial order.

graded :: (Monomial n -> Monomial n -> Ordering) -> Monomial n -> Monomial n -> Ordering

Convert ordering into graded one.

grlex :: MonomialOrder

Graded lexicographical order. This *is* a monomial order.

grevlex :: MonomialOrder

Graded reversed lexicographical order. This *is* a monomial order.

productOrder :: forall ord ord' n m. (IsOrder ord, IsOrder ord', SingRep n) => Proxy (ProductOrder n ord ord') -> Monomial m -> Monomial m -> Ordering

productOrder' :: forall n ord ord' m. (IsOrder ord, IsOrder ord') => SNat n -> ord -> ord' -> Monomial m -> Monomial m -> Ordering

transformMonomial :: (IsOrder o, IsPolynomial k n, IsPolynomial k m) => (Monomial n -> Monomial m) -> OrderedPolynomial k o n -> OrderedPolynomial k o m

data WeightProxy v where

Data.Proxy provides kind-polymorphic Proxy data-type, but due to bug of GHC 7.4.1, It canot be used as kind-polymorphic. So I define another type here.

Constructors

NilWeight :: WeightProxy `[]`

ConsWeight :: SNat n -> WeightProxy v -> WeightProxy (n : v)

weightOrder :: forall ns ord m. (ToWeightVector ns, IsOrder ord) => Proxy (WeightOrder ns ord) -> Monomial m -> Monomial m -> Ordering

totalDegree :: Monomial n -> Int

totalDegree' :: OrderedPolynomial k ord n -> Int

type IsPolynomial r n = (NoetherianRing r, SingRep n, Eq r)

Type-level constraint to check whether it forms polynomial ring or not.

coeff :: (IsOrder order, IsPolynomial r n) => Monomial n -> OrderedPolynomial r order n -> r

coefficient for a degree.

lcmMonomial :: Monomial n -> Monomial n -> Monomial n

sPolynomial :: (IsPolynomial k n, Field k, IsOrder order) => OrderedPolynomial k order n -> OrderedPolynomial k order n -> OrderedPolynomial k order n

polynomial :: (SingRep n, Eq r, NoetherianRing r, IsOrder order) => Map (OrderedMonomial order n) r -> OrderedPolynomial r order n

castMonomial :: (IsOrder o, IsOrder o', SingRep m, n :<= m) => OrderedMonomial o n -> OrderedMonomial o' m

castPolynomial :: (IsPolynomial r n, IsPolynomial r m, SingRep m, IsOrder o, IsOrder o', n :<= m) => OrderedPolynomial r o n -> OrderedPolynomial r o' m

toPolynomial :: (IsOrder order, IsPolynomial r n) => (r, Monomial n) -> OrderedPolynomial r order n

changeOrder :: (Eq (Monomial n), IsOrder o, IsOrder o', SingRep n) => o' -> OrderedPolynomial k o n -> OrderedPolynomial k o' n

changeOrderProxy :: (Eq (Monomial n), IsOrder o, IsOrder o', SingRep n) => Proxy o' -> OrderedPolynomial k o n -> OrderedPolynomial k o' n

scastMonomial :: n :<= m => SNat m -> OrderedMonomial o n -> OrderedMonomial o m

scastPolynomial :: (IsOrder o, IsOrder o', IsPolynomial r n, IsPolynomial r m, n :<= m, SingRep m) => SNat m -> OrderedPolynomial r o n -> OrderedPolynomial r o' m

data OrderedPolynomial r order n

n-ary polynomial ring over some noetherian ring R.

Instances

(Eq r, NoetherianRing r, IsMonomialOrder ord) => Monomorphicable Nat (OrderedPolynomial r ord)

(IsOrder order, IsPolynomial Nat r n) => LeftModule Integer (OrderedPolynomial r order n)

(IsOrder order, IsPolynomial Nat r n) => LeftModule Natural (OrderedPolynomial r order n)

(IsOrder order, IsPolynomial Nat r n) => RightModule Integer (OrderedPolynomial r order n)

(IsOrder order, IsPolynomial Nat r n) => RightModule Natural (OrderedPolynomial r order n)

(NoetherianRing r, Eq r, IsMonomialOrder ord) => Monomorphicable Nat (:.: * Nat Ideal (OrderedPolynomial r ord))

Wrapped (Map (OrderedMonomial order n) r) (Map (OrderedMonomial order' m) q) (OrderedPolynomial r order n) (OrderedPolynomial q order' m)

(Eq r, IsOrder order, IsPolynomial Nat r n) => Eq (OrderedPolynomial r order n)

(IsMonomialOrder order, IsPolynomial Nat r n, Num r) => Num (OrderedPolynomial r order n)

We provide Num instance to use trivial injection R into R[X]. Do not use signum or abs.

(SingRep Nat n, IsOrder order) => Show (OrderedPolynomial Rational order n)

(Eq r, IsPolynomial Nat r n, IsOrder order, Show r) => Show (OrderedPolynomial r order n)

(IsOrder order, IsPolynomial Nat r n) => Commutative (OrderedPolynomial r order n)

(IsOrder order, IsPolynomial Nat r n) => Ring (OrderedPolynomial r order n)

(IsOrder order, IsPolynomial Nat r n) => Rig (OrderedPolynomial r order n)

(IsOrder order, IsPolynomial Nat r n) => Unital (OrderedPolynomial r order n)

(IsOrder order, IsPolynomial Nat r n) => Group (OrderedPolynomial r order n)

(IsOrder order, IsPolynomial Nat r n) => Multiplicative (OrderedPolynomial r order n)

(IsOrder order, IsPolynomial Nat r n) => Semiring (OrderedPolynomial r order n)

(IsOrder order, IsPolynomial Nat r n) => Monoidal (OrderedPolynomial r order n)

(IsOrder order, IsPolynomial Nat r n) => Additive (OrderedPolynomial r order n)

(IsOrder order, IsPolynomial Nat r n) => Abelian (OrderedPolynomial r order n)

(IsOrder order, IsPolynomial Nat r n) => NoetherianRing (OrderedPolynomial r order n)

By Hilbert's finite basis theorem, a polynomial ring over a noetherian ring is also a noetherian ring.

showPolynomialWithVars :: (Eq a, Show a, SingRep n, NoetherianRing a, IsOrder ordering) => [(Int, String)] -> OrderedPolynomial a ordering n -> String

showPolynomialWith :: (Eq a, Show a, SingRep n, NoetherianRing a, IsOrder ordering) => [(Int, String)] -> (a -> Coefficient) -> OrderedPolynomial a ordering n -> String

showRational :: (Integral a, Show a) => Ratio a -> Coefficient

normalize :: (Eq r, IsOrder order, IsPolynomial r n) => OrderedPolynomial r order n -> OrderedPolynomial r order n

injectCoeff :: IsPolynomial r n => r -> OrderedPolynomial r order n

varX :: (NoetherianRing r, SingRep n, One :<= n) => OrderedPolynomial r order n

var :: (NoetherianRing r, SingRep m, S n :<= m) => SNat (S n) -> OrderedPolynomial r order m

getTerms :: OrderedPolynomial k order n -> [(k, Monomial n)]

shiftR :: forall k r n ord. (Field r, IsPolynomial r n, IsPolynomial r (k :+: n), IsOrder ord) => SNat k -> OrderedPolynomial r ord n -> OrderedPolynomial r ord (k :+: n)

orderedBy :: IsOrder o => OrderedPolynomial k o n -> o -> OrderedPolynomial k o n

divs :: Monomial n -> Monomial n -> Bool

tryDiv :: Field r => (r, Monomial n) -> (r, Monomial n) -> (r, Monomial n)

fromList :: SNat n -> [Int] -> Monomial n

convert NAry list into Monomial.

data Coefficient

Constructors

Zero

Negative String

Positive String

Eps

Instances

Eq Coefficient

Ord Coefficient

Show Coefficient

class ToWeightVector vs where

Methods

calcOrderWeight :: Proxy' vs -> Vector Int n -> Int

Instances

ToWeightVector ([] Nat)

(SingRep Nat n, ToWeightVector ns) => ToWeightVector (: Nat n ns)

leadingTerm :: (IsOrder order, IsPolynomial r n) => OrderedPolynomial r order n -> (r, Monomial n)

leadingMonomial :: (IsOrder order, IsPolynomial r n) => OrderedPolynomial r order n -> Monomial n

leadingOrderedMonomial :: (IsOrder order, IsPolynomial r n) => OrderedPolynomial r order n -> OrderedMonomial order n

leadingCoeff :: (IsOrder order, IsPolynomial r n) => OrderedPolynomial r order n -> r

genVars :: forall k o n. (IsPolynomial k (S n), IsOrder o) => SNat (S n) -> [OrderedPolynomial k o (S n)]

sArity :: OrderedPolynomial k ord n -> SNat n

newtype OrderedMonomial ordering n

A wrapper for monomials with a certain (monomial) order.

Constructors

OrderedMonomial

Fields

getMonomial :: Monomial n

Instances

Monomorphicable Nat (OrderedMonomial ord)

Wrapped (Monomial n) (Monomial m) (OrderedMonomial o n) (OrderedMonomial o' m)

Eq (Monomorphic Nat (OrderedMonomial ord))

Eq (Monomial n) => Eq (OrderedMonomial ordering n)

IsMonomialOrder ord => Ord (Monomorphic Nat (OrderedMonomial ord))

(Eq (Monomial n), IsOrder name) => Ord (OrderedMonomial name n)

Special ordering for ordered-monomials.

Wrapped (Map (OrderedMonomial order n) r) (Map (OrderedMonomial order' m) q) (OrderedPolynomial r order n) (OrderedPolynomial q order' m)

newtype OrderedMonomial' ord

Monomorphic representation for monomial.

Constructors

OM'

Fields

getMonomial' :: [Int]

Instances

Eq (OrderedMonomial' k ord)

IsMonomialOrder ord => Ord (OrderedMonomial' * ord)

Read (OrderedMonomial' k ord)

Show (OrderedMonomial' k ord)

data Grevlex

Graded reversed lexicographical order. Same as Graded Revlex.

Constructors

Grevlex

Instances

Eq Grevlex

Ord Grevlex

Show Grevlex

IsMonomialOrder Grevlex

IsOrder Grevlex

data Revlex

Reversed lexicographical order

Constructors

Revlex

Instances

Eq Revlex

Ord Revlex

Show Revlex

IsOrder Revlex

data Lex

Lexicographical order

Constructors

Lex

Instances

Eq Lex

Ord Lex

Show Lex

IsMonomialOrder Lex

IsOrder Lex

SingRep k n => EliminationType k n Lex

data Grlex

Graded lexicographical order. Same as Graded Lex.

Constructors

Grlex

Instances

Eq Grlex

Ord Grlex

Show Grlex

IsMonomialOrder Grlex

IsOrder Grlex

data Graded ord

Graded order from another monomial order.

Constructors

Graded ord

Instances

Eq ord => Eq (Graded ord)

Ord ord => Ord (Graded ord)

Read ord => Read (Graded ord)

Show ord => Show (Graded ord)

IsMonomialOrder ord => IsMonomialOrder (Graded ord)

IsOrder ord => IsOrder (Graded ord)

data ProductOrder n a b where

Constructors

ProductOrder :: SNat n -> ord -> ord' -> ProductOrder n ord ord'

Instances

(SingRep Nat n, IsMonomialOrder ord, IsMonomialOrder ord') => EliminationType Nat n (ProductOrder n ord ord')

(SingRep Nat n, IsMonomialOrder o, IsMonomialOrder o') => IsMonomialOrder (ProductOrder n o o')

(IsOrder ord, IsOrder ord', SingRep Nat n) => IsOrder (ProductOrder n ord ord')

data WeightOrder v ord where

Constructors

WeightOrder :: WeightProxy (v :: [Nat]) -> ord -> WeightOrder v ord

Instances

IsMonomialOrder ord => EliminationType Nat Z (WeightOrder ([] Nat) ord)

(IsMonomialOrder ord, ToWeightVector ns, EliminationType Nat n (WeightOrder ns ord)) => EliminationType Nat (S n) (WeightOrder (: Nat One ns) ord)

(ToWeightVector ws, IsMonomialOrder ord) => IsMonomialOrder (WeightOrder ws ord)

(ToWeightVector ws, IsOrder ord) => IsOrder (WeightOrder ws ord)

class IsOrder ordering where

Class to lookup ordering from its (type-level) name.

Methods

cmpMonomial :: Proxy ordering -> MonomialOrder

Instances

IsOrder Grlex

IsOrder Grevlex

IsOrder Revlex

IsOrder Lex

IsOrder ord => IsOrder (Graded ord)

(SingRep Nat n, IsMonomialOrder ord) => IsOrder (WeightedEliminationOrder n ord)

(ToWeightVector ws, IsOrder ord) => IsOrder (WeightOrder ws ord)

(IsOrder ord, IsOrder ord', SingRep Nat n) => IsOrder (ProductOrder n ord ord')

class IsOrder name => IsMonomialOrder name

Class for Monomial orders.

Instances

IsMonomialOrder Grlex

IsMonomialOrder Grevlex

IsMonomialOrder Lex

IsMonomialOrder ord => IsMonomialOrder (Graded ord)

(SingRep Nat n, IsMonomialOrder ord) => IsMonomialOrder (WeightedEliminationOrder n ord)

(ToWeightVector ws, IsMonomialOrder ord) => IsMonomialOrder (WeightOrder ws ord)

(SingRep Nat n, IsMonomialOrder o, IsMonomialOrder o') => IsMonomialOrder (ProductOrder n o o')