Data.Polynomial

Polynomials

References:

• Monomial order http://en.wikipedia.org/wiki/Monomial_order
• Polynomial class for Ruby http://www.math.kobe-u.ac.jp/~kodama/tips-RubyPoly.html
• constructive-algebra package http://hackage.haskell.org/package/constructive-algebra

Polynomial type

data Polynomial k v

Polynomial over commutative ring r

Instances

Typeable2 Polynomial

(Eq k, Num k) => Variables (Polynomial k)

(Eq k, Eq v) => Eq (Polynomial k v)

(Eq k, Num k, Ord v) => Num (Polynomial k v)

(Ord k, Ord v) => Ord (Polynomial k v)

(Show v, Ord v, Show k) => Show (Polynomial k v)

(NFData k, NFData v) => NFData (Polynomial k v)

(Ord k, Num k, Ord v, PrettyCoeff k, PrettyVar v) => Pretty (Polynomial k v)

(Eq k, Num k, Ord v) => VectorSpace (Polynomial k v)

(Eq k, Num k, Ord v) => AdditiveGroup (Polynomial k v)

(Num c, Ord c, PrettyCoeff c, Ord v, PrettyVar v) => PrettyCoeff (Polynomial c v)

Degree (Polynomial k v)

type UPolynomial r = Polynomial r X

Univariate polynomials over commutative ring r

data X

Constructors

X

Instances

Bounded X

Enum X

Eq X

Data X

Ord X

Read X

Show X

Typeable X

NFData X

PrettyVar X

Conversion

class Variables f where

Methods

var :: Ord v => v -> f v

variables :: Ord v => f v -> Set v

Instances

Variables MonicMonomial

(Eq k, Num k) => Variables (Polynomial k)

constant :: (Eq k, Num k, Ord v) => k -> Polynomial k v

construct a polynomial from a constant

terms :: Polynomial k v -> [Monomial k v]

list of monomials

fromTerms :: (Eq k, Num k, Ord v) => [Monomial k v] -> Polynomial k v

construct a polynomial from a list of monomials

coeffMap :: Polynomial k v -> Map (MonicMonomial v) k

fromCoeffMap :: (Eq k, Num k, Ord v) => Map (MonicMonomial v) k -> Polynomial k v

fromMonomial :: (Eq k, Num k, Ord v) => Monomial k v -> Polynomial k v

construct a polynomial from a monomial

Query

class Degree t where

total degree of a given polynomial

Methods

deg :: t -> Integer

Instances

Degree AReal

Degree of the algebraic number.

If the algebraic number's minimalPolynomial has degree n, then the algebraic number is said to be degree n.

Degree (MonicMonomial v)

Degree (Polynomial k v)

leadingTerm :: (Eq k, Num k, Ord v) => MonomialOrder v -> Polynomial k v -> Monomial k v

leading term with respect to a given monomial order

coeff :: (Num k, Ord v) => MonicMonomial v -> Polynomial k v -> k

lookupCoeff :: Ord v => MonicMonomial v -> Polynomial k v -> Maybe k

isPrimitive :: (Eq k, Num k, ContPP k, Ord v) => Polynomial k v -> Bool

Operations

class ContPP k where

Methods

cont :: Ord v => Polynomial k v -> k

Content of a polynomial

pp :: Ord v => Polynomial k v -> Polynomial k v

Primitive part of a polynomial

Instances

ContPP Integer

Integral r => ContPP (Ratio r)

deriv :: (Eq k, Num k, Ord v) => Polynomial k v -> v -> Polynomial k v

Formal derivative of polynomials

integral :: (Eq k, Fractional k, Ord v) => Polynomial k v -> v -> Polynomial k v

Formal integral of polynomials

eval :: (Num k, Ord v) => (v -> k) -> Polynomial k v -> k

Evaluation

evalA :: forall k v f. (Num k, Ord v, Applicative f) => (v -> f k) -> Polynomial k v -> f k

Evaluation

evalM :: (Num k, Ord v, Monad m) => (v -> m k) -> Polynomial k v -> m k

Evaluation

subst :: (Eq k, Num k, Ord v1, Ord v2) => Polynomial k v1 -> (v1 -> Polynomial k v2) -> Polynomial k v2

Substitution or bind

substA :: forall k v1 v2 f. (Eq k, Num k, Ord v1, Ord v2, Applicative f) => Polynomial k v1 -> (v1 -> f (Polynomial k v2)) -> f (Polynomial k v2)

Substitution or bind

substM :: (Eq k, Num k, Ord v1, Ord v2, Monad m) => Polynomial k v1 -> (v1 -> m (Polynomial k v2)) -> m (Polynomial k v2)

Substitution or bind

isRootOf :: (Eq k, Num k) => k -> UPolynomial k -> Bool

mapVar :: (Eq k, Num k, Ord v1, Ord v2) => (v1 -> v2) -> Polynomial k v1 -> Polynomial k v2

mapCoeff :: (Eq k1, Num k1, Ord v) => (k -> k1) -> Polynomial k v -> Polynomial k1 v

associatedMonicPolynomial :: (Eq r, Fractional r, Ord v) => MonomialOrder v -> Polynomial r v -> Polynomial r v

toUPolynomialOf :: (Ord k, Num k, Ord v) => Polynomial k v -> v -> UPolynomial (Polynomial k v)

polyDiv :: (Eq k, Fractional k) => UPolynomial k -> UPolynomial k -> UPolynomial k

division of univariate polynomials

polyMod :: (Eq k, Fractional k) => UPolynomial k -> UPolynomial k -> UPolynomial k

division of univariate polynomials

polyDivMod :: (Eq k, Fractional k) => UPolynomial k -> UPolynomial k -> (UPolynomial k, UPolynomial k)

division of univariate polynomials

polyGCD :: (Eq k, Fractional k) => UPolynomial k -> UPolynomial k -> UPolynomial k

GCD of univariate polynomials

polyLCM :: (Eq k, Fractional k) => UPolynomial k -> UPolynomial k -> UPolynomial k

LCM of univariate polynomials

prem :: (Eq r, Integral r) => UPolynomial r -> UPolynomial r -> UPolynomial r

pseudo reminder

polyGCD' :: (Eq r, Integral r) => UPolynomial r -> UPolynomial r -> UPolynomial r

GCD of univariate polynomials

polyMDivMod :: forall k v. (Eq k, Fractional k, Ord v) => MonomialOrder v -> Polynomial k v -> [Polynomial k v] -> ([Polynomial k v], Polynomial k v)

Multivariate division algorithm

reduce :: (Eq k, Fractional k, Ord v) => MonomialOrder v -> Polynomial k v -> [Polynomial k v] -> Polynomial k v

Multivariate division algorithm

Monomial

type Monomial k v = (k, MonicMonomial v)

monomialDegree :: Monomial k v -> Integer

monomialProd :: (Num k, Ord v) => Monomial k v -> Monomial k v -> Monomial k v

monomialDivisible :: (Fractional k, Ord v) => Monomial k v -> Monomial k v -> Bool

monomialDiv :: (Fractional k, Ord v) => Monomial k v -> Monomial k v -> Monomial k v

monomialDeriv :: (Eq k, Num k, Ord v) => Monomial k v -> v -> Monomial k v

monomialIntegral :: (Eq k, Fractional k, Ord v) => Monomial k v -> v -> Monomial k v

Monic monomial

data MonicMonomial v

Monic monomials

Instances

Typeable1 MonicMonomial

Variables MonicMonomial

Eq v => Eq (MonicMonomial v)

Ord v => Ord (MonicMonomial v)

(Ord v, Show v) => Show (MonicMonomial v)

NFData v => NFData (MonicMonomial v)

Degree (MonicMonomial v)

mmOne :: MonicMonomial v

mmFromList :: Ord v => [(v, Integer)] -> MonicMonomial v

mmFromMap :: Ord v => Map v Integer -> MonicMonomial v

mmFromIntMap :: IntMap Integer -> MonicMonomial Int

mmToList :: Ord v => MonicMonomial v -> [(v, Integer)]

mmToMap :: MonicMonomial v -> Map v Integer

mmToIntMap :: MonicMonomial Int -> IntMap Integer

mmProd :: Ord v => MonicMonomial v -> MonicMonomial v -> MonicMonomial v

mmDivisible :: Ord v => MonicMonomial v -> MonicMonomial v -> Bool

mmDiv :: Ord v => MonicMonomial v -> MonicMonomial v -> MonicMonomial v

mmDeriv :: Ord v => MonicMonomial v -> v -> (Integer, MonicMonomial v)

mmIntegral :: Ord v => MonicMonomial v -> v -> (Rational, MonicMonomial v)

mmLCM :: Ord v => MonicMonomial v -> MonicMonomial v -> MonicMonomial v

mmGCD :: Ord v => MonicMonomial v -> MonicMonomial v -> MonicMonomial v

mmMapVar :: (Ord v1, Ord v2) => (v1 -> v2) -> MonicMonomial v1 -> MonicMonomial v2

Monomial order

type MonomialOrder v = MonicMonomial v -> MonicMonomial v -> Ordering

lex :: Ord v => MonomialOrder v

Lexicographic order

revlex :: Ord v => MonicMonomial v -> MonicMonomial v -> Ordering

Reverse lexicographic order Note that revlex is NOT a monomial order.

grlex :: Ord v => MonomialOrder v

graded lexicographic order

grevlex :: Ord v => MonomialOrder v

graded reverse lexicographic order

Pretty Printing

data PrintOptions k v

Constructors

PrintOptions

Fields

pOptPrintVar :: PrettyLevel -> Rational -> v -> Doc

pOptPrintCoeff :: PrettyLevel -> Rational -> k -> Doc

pOptIsNegativeCoeff :: k -> Bool

pOptMonomialOrder :: MonomialOrder v

defaultPrintOptions :: (PrettyCoeff k, PrettyVar v, Ord v) => PrintOptions k v

prettyPrint :: (Ord k, Num k, Ord v) => PrintOptions k v -> PrettyLevel -> Rational -> Polynomial k v -> Doc

class PrettyCoeff a where

Methods

pPrintCoeff :: PrettyLevel -> Rational -> a -> Doc

isNegativeCoeff :: a -> Bool

Instances

PrettyCoeff Integer

PrettyCoeff AReal

(PrettyCoeff a, Integral a) => PrettyCoeff (Ratio a)

PrettyCoeff (PrimeField a)

(Num c, Ord c, PrettyCoeff c, Ord v, PrettyVar v) => PrettyCoeff (Polynomial c v)

class PrettyVar a where

Methods

pPrintVar :: PrettyLevel -> Rational -> a -> Doc

Instances

PrettyVar Int

PrettyVar X