ToySolver.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

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)

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

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

(Hashable k, Hashable v) => Hashable (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)

Typeable (* -> * -> *) Polynomial

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

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

type Scalar (Polynomial k v) = k

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 terms

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

construct a polynomial from a list of terms

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 singlet term

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

Look up a coefficient for a given monomial. If no such term exists, it returns 0.

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

Look up a coefficient for a given monomial. If no such term exists, it returns Nothing.

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

a polynomial is called primitive if the greatest common divisor of its coefficients is 1.

Operations

class Factor a where

Prime 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

Transform polynomial coefficients.

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

Transform a polynomial into a monic polynomial with respect to the given monomial order.

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

Convert K[x,x1,x2,…] into K[x1,x2,…][x].

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

divModMP cmp f [g1,g2,..] returns a pair ([q1,q2,…],r) such that

• f = g1*q1 + g2*q2 + .. + r and
• g1, g2, .. do not divide r.

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

Multivariate division algorithm

reduce cmp f gs = snd (divModMP cmp f gs)

Univariate polynomials

type UPolynomial r = Polynomial r X

Univariate polynomials over commutative ring r

data X

Variable "x"

Constructors

X

Instances

Bounded X

Enum X

Eq X

Data X

Ord X

Read X

Show X

NFData X

Hashable X

PrettyVar X

Typeable * 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 infixl 7

division of univariate polynomials

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

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

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

Is the number a root of the polynomial?

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

Is the polynomial square free?

nat :: MonomialOrder X

Natural ordering x^0 < x^1 < x^2 .. is the unique monomial order for univariate polynomials.

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

Eq v => Eq (Monomial v)

Ord v => Ord (Monomial v)

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

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

NFData v => NFData (Monomial v)

Hashable v => Hashable (Monomial v)

Degree (Monomial v)

Ord v => Vars (Monomial v) v

Ord v => Var (Monomial v) v

Typeable (* -> *) Monomial

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

Minimal complete definition

pPrintCoeff

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