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 r v

Polynomial over commutative ring r

Instances

Typeable2 Polynomial

SQFree (UPolynomial Integer)

SQFree (UPolynomial Rational)

Nat p => SQFree (UPolynomial (PrimeField p))

Factor (UPolynomial Integer)

Factor (UPolynomial Rational)

Nat p => Factor (UPolynomial (PrimeField p))

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

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

(Ord r, Ord v) => Ord (Polynomial r 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)

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

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

Conversion

class Vars a v => Var a v | a -> v where

Methods

var :: v -> a

Instances

Ord v => Var (Monomial v) v

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

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

construct a polynomial from a constant

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

list of monomials

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

construct a polynomial from a list of monomials

coeffMap :: Polynomial r v -> Map (Monomial v) r

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

fromTerm :: (Eq k, Num k, Ord v) => Term 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 (Monomial v)

Degree (Polynomial k v)

class Ord v => Vars a v | a -> v where

Methods

vars :: a -> Set v

Instances

Ord v => Vars (Monomial v) v

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

lt :: (Eq k, Num k, Ord v) => MonomialOrder v -> Polynomial k v -> Term k v

leading term with respect to a given monomial order

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

leading coefficient with respect to a given monomial order

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

leading monomial with respect to a given monomial order

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

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

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

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

Operations

class Factor a where

Factorization of polynomials

Methods

factor :: a -> [(a, Integer)]

factor a polynomial p into p1 ^ n1 + p2 ^ n2 + .. and return a list [(p1,n1), (p2,n2), ..].

Instances

Factor (UPolynomial Integer)

Factor (UPolynomial Rational)

Nat p => Factor (UPolynomial (PrimeField p))

class SQFree a where

Square-free factorization of polynomials

Methods

sqfree :: a -> [(a, Integer)]

factor a polynomial p into p1 ^ n1 + p2 ^ n2 + .. and return a list [(p1,n1), (p2,n2), ..].

Instances

SQFree (UPolynomial Integer)

SQFree (UPolynomial Rational)

Nat p => SQFree (UPolynomial (PrimeField p))

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

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

Substitution or bind

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

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

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

Univariate polynomials

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

SQFree (UPolynomial Integer)

SQFree (UPolynomial Rational)

Nat p => SQFree (UPolynomial (PrimeField p))

Factor (UPolynomial Integer)

Factor (UPolynomial Rational)

Nat p => Factor (UPolynomial (PrimeField p))

type UTerm k = Term k X

type UMonomial = Monomial X

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

division of univariate polynomials

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

division of univariate polynomials

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

division of univariate polynomials

divides :: (Eq k, Fractional k) => UPolynomial k -> UPolynomial k -> Bool

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

GCD of univariate polynomials

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

LCM of univariate polynomials

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

Extended GCD algorithm

pdivMod :: (Eq r, Num r) => UPolynomial r -> UPolynomial r -> (r, UPolynomial r, UPolynomial r)

pseudo division

pdiv :: (Eq r, Num r) => UPolynomial r -> UPolynomial r -> UPolynomial r

pseudo quotient

pmod :: (Eq r, Num r) => UPolynomial r -> UPolynomial r -> UPolynomial r

pseudo reminder

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

GCD of univariate polynomials

isSquareFree :: (Eq k, Fractional k) => UPolynomial k -> Bool

Term

type Term k v = (k, Monomial v)

tdeg :: Term k v -> Integer

tmult :: (Num k, Ord v) => Term k v -> Term k v -> Term k v

tdivides :: (Fractional k, Ord v) => Term k v -> Term k v -> Bool

tdiv :: (Fractional k, Ord v) => Term k v -> Term k v -> Term k v

tderiv :: (Eq k, Num k, Ord v) => Term k v -> v -> Term k v

tintegral :: (Eq k, Fractional k, Ord v) => Term k v -> v -> Term k v

Monic monomial

data Monomial v

Monic monomials

Instances

Typeable1 Monomial

Eq v => Eq (Monomial v)

Ord v => Ord (Monomial v)

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

NFData v => NFData (Monomial v)

Degree (Monomial v)

Ord v => Vars (Monomial v) v

Ord v => Var (Monomial v) v

mone :: Monomial v

mfromIndices :: Ord v => [(v, Integer)] -> Monomial v

mfromIndicesMap :: Ord v => Map v Integer -> Monomial v

mindices :: Ord v => Monomial v -> [(v, Integer)]

mindicesMap :: Monomial v -> Map v Integer

mmult :: Ord v => Monomial v -> Monomial v -> Monomial v

mpow :: Ord v => Monomial v -> Integer -> Monomial v

mdivides :: Ord v => Monomial v -> Monomial v -> Bool

mdiv :: Ord v => Monomial v -> Monomial v -> Monomial v

mderiv :: Ord v => Monomial v -> v -> (Integer, Monomial v)

mintegral :: Ord v => Monomial v -> v -> (Rational, Monomial v)

mlcm :: Ord v => Monomial v -> Monomial v -> Monomial v

mgcd :: Ord v => Monomial v -> Monomial v -> Monomial v

mcoprime :: Ord v => Monomial v -> Monomial v -> Bool

Monomial order

type MonomialOrder v = Monomial v -> Monomial v -> Ordering

lex :: Ord v => MonomialOrder v

Lexicographic order

revlex :: Ord v => Monomial v -> Monomial 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