Algebra.Ring.Polynomial.Monomial

Documentation

type Monomial n = Sized' n Int

N-ary Monomial. IntMap contains degrees for each x_i- type Monomial (n :: Nat) = Sized n Int

newtype OrderedMonomial ordering n

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

Constructors

OrderedMonomial

Fields

• getMonomial :: Monomial n

Instances

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

Methods

(==) :: OrderedMonomial k ordering n -> OrderedMonomial k ordering n -> Bool

(/=) :: OrderedMonomial k ordering n -> OrderedMonomial k ordering n -> Bool

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

Special ordering for ordered-monomials.

Methods

compare :: OrderedMonomial * name n -> OrderedMonomial * name n -> Ordering

(<) :: OrderedMonomial * name n -> OrderedMonomial * name n -> Bool

(<=) :: OrderedMonomial * name n -> OrderedMonomial * name n -> Bool

(>) :: OrderedMonomial * name n -> OrderedMonomial * name n -> Bool

(>=) :: OrderedMonomial * name n -> OrderedMonomial * name n -> Bool

max :: OrderedMonomial * name n -> OrderedMonomial * name n -> OrderedMonomial * name n

min :: OrderedMonomial * name n -> OrderedMonomial * name n -> OrderedMonomial * name n

KnownNat n => Show (OrderedMonomial k ord n)

Methods

showsPrec :: Int -> OrderedMonomial k ord n -> ShowS

show :: OrderedMonomial k ord n -> String

showList :: [OrderedMonomial k ord n] -> ShowS

KnownNat n => Division (OrderedMonomial k ord n)

Methods

recip :: OrderedMonomial k ord n -> OrderedMonomial k ord n

(/) :: OrderedMonomial k ord n -> OrderedMonomial k ord n -> OrderedMonomial k ord n

(\\) :: OrderedMonomial k ord n -> OrderedMonomial k ord n -> OrderedMonomial k ord n

(^) :: Integral n => OrderedMonomial k ord n -> n -> OrderedMonomial k ord n

KnownNat n => Unital (OrderedMonomial k ord n)

Methods

one :: OrderedMonomial k ord n

pow :: OrderedMonomial k ord n -> Natural -> OrderedMonomial k ord n

productWith :: Foldable f => (a -> OrderedMonomial k ord n) -> f a -> OrderedMonomial k ord n

Multiplicative (OrderedMonomial k ord n)

Methods

(*) :: OrderedMonomial k ord n -> OrderedMonomial k ord n -> OrderedMonomial k ord n

pow1p :: OrderedMonomial k ord n -> Natural -> OrderedMonomial k ord n

productWith1 :: Foldable1 f => (a -> OrderedMonomial k ord n) -> f a -> OrderedMonomial k ord n

Hashable (Monomial n) => Hashable (OrderedMonomial k ordering n)

Methods

hashWithSalt :: Int -> OrderedMonomial k ordering n -> Int

hash :: OrderedMonomial k ordering n -> Int

NFData (OrderedMonomial k ordering n)

Methods

rnf :: OrderedMonomial k ordering n -> ()

Wrapped (OrderedMonomial k ordering0 n0)

Associated Types

type Unwrapped (OrderedMonomial k ordering0 n0) :: *

Methods

_Wrapped' :: Iso' (OrderedMonomial k ordering0 n0) (Unwrapped (OrderedMonomial k ordering0 n0))

(~) * (OrderedMonomial k1 ordering0 n0) t0 => Rewrapped (OrderedMonomial k ordering1 n1) t0

type Unwrapped (OrderedMonomial k ordering0 n0)

type Unwrapped (OrderedMonomial k ordering0 n0) = Monomial n0

class IsOrder n ordering where

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

Minimal complete definition

cmpMonomial

Methods

cmpMonomial :: Proxy ordering -> MonomialOrder n

Instances

IsOrder n Grlex

Methods

cmpMonomial :: Proxy * Grlex -> MonomialOrder n

IsOrder n Lex

Methods

cmpMonomial :: Proxy * Lex -> MonomialOrder n

IsOrder n Revlex

Methods

cmpMonomial :: Proxy * Revlex -> MonomialOrder n

IsOrder n Grevlex

Methods

cmpMonomial :: Proxy * Grevlex -> MonomialOrder n

IsOrder n ord => IsOrder n (Graded ord)

Methods

cmpMonomial :: Proxy * (Graded ord) -> MonomialOrder n

(KnownNat n, IsOrder n ord, SingI [Nat] ws) => IsOrder n (WeightOrder ws ord)

Methods

cmpMonomial :: Proxy * (WeightOrder ws ord) -> MonomialOrder n

(IsOrder n ord, IsOrder m ord', KnownNat m, KnownNat n, (~) Nat k ((+) n m)) => IsOrder k (ProductOrder n m ord ord')

Methods

cmpMonomial :: Proxy * (ProductOrder n m ord ord') -> MonomialOrder k

class IsOrder n name => IsMonomialOrder n name

Class for Monomial orders.

Instances

IsMonomialOrder n Lex

IsMonomialOrder n Grevlex

IsMonomialOrder n Grlex

IsMonomialOrder n ord => IsMonomialOrder n (Graded ord)

(KnownNat k, SingI [Nat] ws, IsMonomialOrder k ord) => IsMonomialOrder k (WeightOrder ws ord)

(KnownNat n, KnownNat m, IsMonomialOrder n o, IsMonomialOrder m o', (~) Nat k ((+) n m)) => IsMonomialOrder k (ProductOrder n m o o')

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

type IsStrongMonomialOrder ord = Forall (IsMonomialOrder' ord)

Monomial ordering which can do with monomials of arbitrary large arity.

isRelativelyPrime :: OrderedMonomial ord n -> OrderedMonomial ord n -> Bool

totalDegree :: OrderedMonomial ord n -> Int

data ProductOrder n m a b where

Constructors

ProductOrder :: Sing n -> Sing m -> ord -> ord' -> ProductOrder n m ord ord'

Instances

(KnownNat n, KnownNat m, IsMonomialOrder n ord, IsMonomialOrder m ord', (~) Nat k ((+) n m), KnownNat k) => EliminationType Nat k n (ProductOrder n m ord ord')

(KnownNat n, KnownNat m, IsMonomialOrder n o, IsMonomialOrder m o', (~) Nat k ((+) n m)) => IsMonomialOrder k (ProductOrder n m o o')

(IsOrder n ord, IsOrder m ord', KnownNat m, KnownNat n, (~) Nat k ((+) n m)) => IsOrder k (ProductOrder n m ord ord')

Methods

cmpMonomial :: Proxy * (ProductOrder n m ord ord') -> MonomialOrder k

productOrder :: forall ord ord' n m. (IsOrder n ord, IsOrder m ord', KnownNat n, KnownNat m) => Proxy (ProductOrder n m ord ord') -> MonomialOrder (n + m)

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

type WeightProxy v = SList v

data WeightOrder v ord where

Constructors

WeightOrder :: SList (v :: [Nat]) -> Proxy ord -> WeightOrder v ord

Instances

(IsMonomialOrder k ord, (~) [Nat] ones (Replicate Nat n 1), SingI [Nat] ones, (~) Bool ((:<=) Nat (Length Nat ones) k) True, KnownNat k) => EliminationType Nat k n (WeightOrder ones ord)

(KnownNat k, SingI [Nat] ws, IsMonomialOrder k ord) => IsMonomialOrder k (WeightOrder ws ord)

(KnownNat n, IsOrder n ord, SingI [Nat] ws) => IsOrder n (WeightOrder ws ord)

Methods

cmpMonomial :: Proxy * (WeightOrder ws ord) -> MonomialOrder n

gcdMonomial :: OrderedMonomial ord n -> OrderedMonomial ord n -> OrderedMonomial ord n

divs :: OrderedMonomial ord n -> OrderedMonomial ord n -> Bool

isPowerOf :: KnownNat n => OrderedMonomial ord n -> OrderedMonomial ord n -> Bool

tryDiv :: Field r => (r, OrderedMonomial ord n) -> (r, OrderedMonomial ord n) -> (r, OrderedMonomial ord n)

lcmMonomial :: OrderedMonomial ord n -> OrderedMonomial ord n -> OrderedMonomial ord n

data Lex

Lexicographical order

Constructors

Lex

Instances

Eq Lex

Methods

(==) :: Lex -> Lex -> Bool

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

Ord Lex

Methods

compare :: Lex -> Lex -> Ordering

(<) :: Lex -> Lex -> Bool

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

(>) :: Lex -> Lex -> Bool

(>=) :: Lex -> Lex -> Bool

max :: Lex -> Lex -> Lex

min :: Lex -> Lex -> Lex

Show Lex

Methods

showsPrec :: Int -> Lex -> ShowS

show :: Lex -> String

showList :: [Lex] -> ShowS

IsMonomialOrder n Lex

IsOrder n Lex

Methods

cmpMonomial :: Proxy * Lex -> MonomialOrder n

KnownNat n => EliminationType k n m Lex

class (IsMonomialOrder n ord, KnownNat n) => EliminationType n m ord

Monomial order which can be use to calculate n-th elimination ideal of m-ary polynomial. This should judge monomial to be bigger if it contains variables to eliminate.

Instances

KnownNat n => EliminationType k n m Lex

(IsMonomialOrder k ord, (~) [Nat] ones (Replicate Nat n 1), SingI [Nat] ones, (~) Bool ((:<=) Nat (Length Nat ones) k) True, KnownNat k) => EliminationType Nat k n (WeightOrder ones ord)

(KnownNat n, KnownNat m, IsMonomialOrder n ord, IsMonomialOrder m ord', (~) Nat k ((+) n m), KnownNat k) => EliminationType Nat k n (ProductOrder n m ord ord')

type EliminationOrder n m = ProductOrder n m Grevlex Grevlex

type WeightedEliminationOrder n ord = WeightOrder (Replicate n 1) ord

eliminationOrder :: SNat n -> SNat m -> EliminationOrder n m

weightedEliminationOrder :: SNat n -> WeightedEliminationOrder n Grevlex

lex :: MonomialOrder n

Lexicographical order. This *is* a monomial order.

revlex :: MonomialOrder n

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

graded :: MonomialOrder n -> MonomialOrder n

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.

weightOrder :: forall n ns ord. (KnownNat n, IsOrder n ord, SingI ns) => Proxy (WeightOrder ns ord) -> MonomialOrder n

data Grevlex

Graded reversed lexicographical order. Same as Graded Revlex.

Constructors

Grevlex

Instances

Eq Grevlex

Methods

(==) :: Grevlex -> Grevlex -> Bool

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

Ord Grevlex

Methods

compare :: Grevlex -> Grevlex -> Ordering

(<) :: Grevlex -> Grevlex -> Bool

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

(>) :: Grevlex -> Grevlex -> Bool

(>=) :: Grevlex -> Grevlex -> Bool

max :: Grevlex -> Grevlex -> Grevlex

min :: Grevlex -> Grevlex -> Grevlex

Show Grevlex

Methods

showsPrec :: Int -> Grevlex -> ShowS

show :: Grevlex -> String

showList :: [Grevlex] -> ShowS

IsMonomialOrder n Grevlex

IsOrder n Grevlex

Methods

cmpMonomial :: Proxy * Grevlex -> MonomialOrder n

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

convert NAry list into Monomial.

data Revlex

Reversed lexicographical order

Constructors

Revlex

Instances

Eq Revlex

Methods

(==) :: Revlex -> Revlex -> Bool

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

Ord Revlex

Methods

compare :: Revlex -> Revlex -> Ordering

(<) :: Revlex -> Revlex -> Bool

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

(>) :: Revlex -> Revlex -> Bool

(>=) :: Revlex -> Revlex -> Bool

max :: Revlex -> Revlex -> Revlex

min :: Revlex -> Revlex -> Revlex

Show Revlex

Methods

showsPrec :: Int -> Revlex -> ShowS

show :: Revlex -> String

showList :: [Revlex] -> ShowS

IsOrder n Revlex

Methods

cmpMonomial :: Proxy * Revlex -> MonomialOrder n

data Grlex

Graded lexicographical order. Same as Graded Lex.

Constructors

Grlex

Instances

Eq Grlex

Methods

(==) :: Grlex -> Grlex -> Bool

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

Ord Grlex

Methods

compare :: Grlex -> Grlex -> Ordering

(<) :: Grlex -> Grlex -> Bool

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

(>) :: Grlex -> Grlex -> Bool

(>=) :: Grlex -> Grlex -> Bool

max :: Grlex -> Grlex -> Grlex

min :: Grlex -> Grlex -> Grlex

Show Grlex

Methods

showsPrec :: Int -> Grlex -> ShowS

show :: Grlex -> String

showList :: [Grlex] -> ShowS

IsMonomialOrder n Grlex

IsOrder n Grlex

Methods

cmpMonomial :: Proxy * Grlex -> MonomialOrder n

data Graded ord

Graded order from another monomial order.

Constructors

Graded ord

Instances

IsMonomialOrder n ord => IsMonomialOrder n (Graded ord)

IsOrder n ord => IsOrder n (Graded ord)

Methods

cmpMonomial :: Proxy * (Graded ord) -> MonomialOrder n

Eq ord => Eq (Graded ord)

Methods

(==) :: Graded ord -> Graded ord -> Bool

(/=) :: Graded ord -> Graded ord -> Bool

Ord ord => Ord (Graded ord)

Methods

compare :: Graded ord -> Graded ord -> Ordering

(<) :: Graded ord -> Graded ord -> Bool

(<=) :: Graded ord -> Graded ord -> Bool

(>) :: Graded ord -> Graded ord -> Bool

(>=) :: Graded ord -> Graded ord -> Bool

max :: Graded ord -> Graded ord -> Graded ord

min :: Graded ord -> Graded ord -> Graded ord

Read ord => Read (Graded ord)

Methods

readsPrec :: Int -> ReadS (Graded ord)

readList :: ReadS [Graded ord]

readPrec :: ReadPrec (Graded ord)

readListPrec :: ReadPrec [Graded ord]

Show ord => Show (Graded ord)

Methods

showsPrec :: Int -> Graded ord -> ShowS

show :: Graded ord -> String

showList :: [Graded ord] -> ShowS

castMonomial :: KnownNat m => OrderedMonomial o n -> OrderedMonomial o' m

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

varMonom :: SNat n -> Ordinal n -> Monomial n

changeMonomialOrder :: o' -> OrderedMonomial ord n -> OrderedMonomial o' n

changeMonomialOrderProxy :: Proxy o' -> OrderedMonomial ord n -> OrderedMonomial o' n

sOnes :: Sing n -> Sing (Replicate n 1)

withStrongMonomialOrder :: forall ord n r proxy proxy'. IsStrongMonomialOrder ord => proxy ord -> proxy' n -> (IsMonomialOrder n ord => r) -> r

cmpAnyMonomial :: IsStrongMonomialOrder ord => Proxy ord -> Monomial n -> Monomial m -> Ordering

Comparing monomials with different arity, padding with 0 at bottom of the shorter monomial to make the length equal.

orderMonomial :: proxy ord -> Monomial n -> OrderedMonomial ord n

Orphan instances

Ord (Monomial n)

For simplicity, we choose grevlex for the default monomial ordering (for the sake of efficiency).

Methods

compare :: Monomial n -> Monomial n -> Ordering

(<) :: Monomial n -> Monomial n -> Bool

(<=) :: Monomial n -> Monomial n -> Bool

(>) :: Monomial n -> Monomial n -> Bool

(>=) :: Monomial n -> Monomial n -> Bool

max :: Monomial n -> Monomial n -> Monomial n

min :: Monomial n -> Monomial n -> Monomial n