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 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 Order a

Instances

Order Bool

Order Int

Order Int8

Order Int16

Order Int32

Order Int64

Order Integer

Order Word

Order Word8

Order Word16

Order Word32

Order Word64

Order ()

Order Natural

Ord a => Order (Set a)

(Order a, Order b) => Order (a, b)

(Order a, Order b, Order c) => Order (a, b, c)

(Order a, Order b, Order c, Order d) => Order (a, b, c, d)

(Order a, Order b, Order c, Order d, Order e) => Order (a, b, c, d, e)

lex :: MonomialOrder n

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 n

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

grevlex :: MonomialOrder n

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

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

type IsPolynomial r n = (NoetherianRing r, Sing 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 :: (Sing n, Eq r, NoetherianRing r, IsOrder order) => Map (OrderedMonomial order n) r -> OrderedPolynomial r order n

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

castPolynomial :: (IsPolynomial r n, IsPolynomial r m, Sing 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', Sing n) => 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, Sing 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

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

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

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

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

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

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

(IsMonomialOrder order, IsPolynomial 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.

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

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

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

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

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

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

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

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

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

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

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

(IsOrder order, IsPolynomial 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, Sing n, NoetherianRing a, IsOrder ordering) => [(Int, String)] -> OrderedPolynomial a ordering n -> String

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, Sing n, One :<= n) => OrderedPolynomial r order n

var :: (NoetherianRing r, Sing 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)

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.

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

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

sDegree :: 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

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

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

(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)

data Grevlex

Constructors

Grevlex

Instances

Eq Grevlex

Ord Grevlex

Show Grevlex

IsMonomialOrder Grevlex

IsOrder Grevlex

data Revlex

Constructors

Revlex

Instances

Eq Revlex

Ord Revlex

Show Revlex

IsOrder Revlex

data Lex

Constructors

Lex

Instances

Eq Lex

Ord Lex

Show Lex

IsMonomialOrder Lex

IsOrder Lex

data Grlex

Constructors

Grlex

Instances

Eq Grlex

Ord Grlex

Show Grlex

IsMonomialOrder Grlex

IsOrder Grlex

class IsOrder ordering

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

Instances

IsOrder Revlex

IsOrder Grlex

IsOrder Lex

IsOrder Grevlex

class IsOrder name => IsMonomialOrder name

Class for Monomial orders.

Instances

IsMonomialOrder Grlex

IsMonomialOrder Lex

IsMonomialOrder Grevlex