toysolver-0.1.0: Assorted decision procedures for SAT, Max-SAT, PB, MIP, etc

Copyright(c) Masahiro Sakai 2012-2013
LicenseBSD-style
Maintainermasahiro.sakai@gmail.com
Stabilityprovisional
Portabilityportable
Safe HaskellNone
LanguageHaskell2010

ToySolver.Data.Polynomial

Contents

Description

Synopsis

Polynomial type

data Polynomial r v Source

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 Source

Methods

var :: v -> a Source

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 Source

construct a polynomial from a constant

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

list of terms

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

construct a polynomial from a list of terms

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

fromTerm :: (Eq k, Num k, Ord v) => Term k v -> Polynomial k v Source

construct a polynomial from a singlet term

Query

class Degree t where Source

total degree of a given polynomial

Methods

deg :: t -> Integer Source

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 Source

Methods

vars :: a -> Set v Source

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 Source

leading term with respect to a given monomial order

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

leading coefficient with respect to a given monomial order

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

leading monomial with respect to a given monomial order

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

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 Source

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 Source

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

Operations

class Factor a where Source

Prime factorization of polynomials

Methods

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

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

class SQFree a where Source

Square-free factorization of polynomials

Methods

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

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

class ContPP k where Source

Methods

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

Content of a polynomial

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

Primitive part of a polynomial

Instances

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

Formal derivative of polynomials

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

Formal integral of polynomials

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

Evaluation

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

Substitution or bind

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

Transform polynomial coefficients.

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

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

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

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 Source

Multivariate division algorithm

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

Univariate polynomials

type UPolynomial r = Polynomial r X Source

Univariate polynomials over commutative ring r

type UTerm k = Term k X Source

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

division of univariate polynomials

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

division of univariate polynomials

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

division of univariate polynomials

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

GCD of univariate polynomials

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

LCM of univariate polynomials

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

Extended GCD algorithm

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

pseudo division

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

pseudo quotient

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

pseudo reminder

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

GCD of univariate polynomials

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

Is the number a root of the polynomial?

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

Is the polynomial square free?

nat :: MonomialOrder X Source

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

Term

type Term k v = (k, Monomial v) Source

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

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

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

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

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

Monic monomial

data Monomial v Source

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 

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

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

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

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

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

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

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

Monomial order

lex :: Ord v => MonomialOrder v Source

Lexicographic order

revlex :: Ord v => Monomial v -> Monomial v -> Ordering Source

Reverse lexicographic order.

Note that revlex is NOT a monomial order.

grlex :: Ord v => MonomialOrder v Source

Graded lexicographic order

grevlex :: Ord v => MonomialOrder v Source

Graded reverse lexicographic order

Pretty Printing

class PrettyVar a where Source

Methods

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

Instances