Copyright	(c) Masahiro Sakai 2012-2013
License	BSD-style
Maintainer	masahiro.sakai@gmail.com
Stability	provisional
Portability	portable
Safe Haskell	Safe-Inferred
Language	Haskell2010

ToySolver.Data.Polynomial

Contents

Polynomial type
Conversion
Query
Operations
Univariate polynomials
Term
Monic monomial
Monomial order
Pretty Printing

Description

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

Synopsis

data Polynomial r v
class Vars a v => Var a v | a -> v where
- var :: v -> a
constant :: (Eq k, Num k) => k -> Polynomial k v
terms :: Polynomial k v -> [Term k v]
fromTerms :: (Eq k, Num k, Ord v) => [Term k v] -> Polynomial k v
coeffMap :: Polynomial r v -> Map (Monomial v) r
fromCoeffMap :: (Eq k, Num k) => Map (Monomial v) k -> Polynomial k v
fromTerm :: (Eq k, Num k) => Term k v -> Polynomial k v
class Degree t where
- deg :: t -> Integer
class Ord v => Vars a v | a -> v where
- vars :: a -> Set v
lt :: Num k => MonomialOrder v -> Polynomial k v -> Term k v
lc :: Num k => MonomialOrder v -> Polynomial k v -> k
lm :: Num k => MonomialOrder v -> Polynomial k v -> Monomial v
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
class Factor a where
- factor :: a -> [(a, Integer)]
class SQFree a where
- sqfree :: a -> [(a, Integer)]
class ContPP k where
- type PPCoeff k
- cont :: Ord v => Polynomial k v -> k
- pp :: Ord v => Polynomial k v -> Polynomial (PPCoeff k) v
deriv :: (Eq k, Num k, Ord v) => Polynomial k v -> v -> Polynomial k v
integral :: (Eq k, Fractional k, Ord v) => Polynomial k v -> v -> Polynomial k v
eval :: Num k => (v -> k) -> Polynomial k v -> k
subst :: (Eq k, Num k, Ord v2) => Polynomial k v1 -> (v1 -> Polynomial k v2) -> Polynomial k v2
mapCoeff :: (Eq k1, Num k1) => (k -> k1) -> Polynomial k v -> Polynomial k1 v
toMonic :: (Eq r, Fractional r) => 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)
reduce :: (Eq k, Fractional k, Ord v) => MonomialOrder v -> Polynomial k v -> [Polynomial k v] -> Polynomial k v
type UPolynomial r = Polynomial r X
data X = X
type UTerm k = Term k X
type UMonomial = Monomial X
div :: (Eq k, Fractional k) => UPolynomial k -> UPolynomial k -> UPolynomial k
mod :: (Eq k, Fractional k) => UPolynomial k -> UPolynomial k -> UPolynomial k
divMod :: (Eq k, Fractional k) => UPolynomial k -> UPolynomial k -> (UPolynomial k, UPolynomial k)
divides :: (Eq k, Fractional k) => UPolynomial k -> UPolynomial k -> Bool
gcd :: (Eq k, Fractional k) => UPolynomial k -> UPolynomial k -> UPolynomial k
lcm :: (Eq k, Fractional k) => UPolynomial k -> UPolynomial k -> UPolynomial k
exgcd :: (Eq k, Fractional k) => UPolynomial k -> UPolynomial k -> (UPolynomial k, UPolynomial k, UPolynomial k)
pdivMod :: (Eq r, Num r) => UPolynomial r -> UPolynomial r -> (r, UPolynomial r, UPolynomial r)
pdiv :: (Eq r, Num r) => UPolynomial r -> UPolynomial r -> UPolynomial r
pmod :: (Eq r, Num r) => UPolynomial r -> UPolynomial r -> UPolynomial r
gcd' :: Integral r => UPolynomial r -> UPolynomial r -> UPolynomial r
isRootOf :: (Eq k, Num k) => k -> UPolynomial k -> Bool
isSquareFree :: (Eq k, Fractional k) => UPolynomial k -> Bool
nat :: MonomialOrder X
eisensteinsCriterion :: (ContPP k, PPCoeff k ~ Integer) => UPolynomial k -> Bool
type Term k v = (k, Monomial v)
tdeg :: Term k v -> Integer
tscale :: Num k => k -> Term k v -> Term k v
tmult :: (Num k, Ord v) => Term k v -> Term k v -> Term k v
tdivides :: Ord v => Term k v -> Term k v -> Bool
tdiv :: (Fractional k, Ord v) => Term k v -> Term k v -> Term k v
tderiv :: (Num k, Ord v) => Term k v -> v -> Term k v
tintegral :: (Fractional k, Ord v) => Term k v -> v -> Term k v
data Monomial v
mone :: Monomial v
mfromIndices :: Ord v => [(v, Integer)] -> Monomial v
mfromIndicesMap :: Ord v => Map v Integer -> Monomial v
mindices :: 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
type MonomialOrder v = Monomial v -> Monomial v -> Ordering
lex :: Ord v => MonomialOrder v
revlex :: Ord v => Monomial v -> Monomial v -> Ordering
grlex :: Ord v => MonomialOrder v
grevlex :: Ord v => MonomialOrder v
data PrintOptions k v = PrintOptions {
- pOptPrintVar :: PrettyLevel -> Rational -> v -> Doc
- pOptPrintCoeff :: PrettyLevel -> Rational -> k -> Doc
- pOptIsNegativeCoeff :: k -> Bool
- pOptMonomialOrder :: MonomialOrder v
}
prettyPrint :: (Ord k, Num k) => PrintOptions k v -> PrettyLevel -> Rational -> Polynomial k v -> Doc
class PrettyCoeff a where
- pPrintCoeff :: PrettyLevel -> Rational -> a -> Doc
- isNegativeCoeff :: a -> Bool
class PrettyVar a where
- pPrintVar :: PrettyLevel -> Rational -> a -> Doc

Polynomial type

data Polynomial r v Source #

Polynomial over commutative ring r

Instances

Instances details

Factor (UPolynomial Rational) Source #
Instance details Defined in ToySolver.Data.Polynomial.Factorization.Rational Methods factor :: UPolynomial Rational -> [(UPolynomial Rational, Integer)] Source #
KnownNat p => Factor (UPolynomial (PrimeField p)) Source #
Instance details Defined in ToySolver.Data.Polynomial.Factorization.FiniteField Methods factor :: UPolynomial (PrimeField p) -> [(UPolynomial (PrimeField p), Integer)] Source #
Factor (UPolynomial Integer) Source #
Instance details Defined in ToySolver.Data.Polynomial.Factorization.Integer Methods factor :: UPolynomial Integer -> [(UPolynomial Integer, Integer)] Source #
SQFree (UPolynomial Rational) Source #
Instance details Defined in ToySolver.Data.Polynomial.Factorization.SquareFree Methods sqfree :: UPolynomial Rational -> [(UPolynomial Rational, Integer)] Source #
KnownNat p => SQFree (UPolynomial (PrimeField p)) Source #
Instance details Defined in ToySolver.Data.Polynomial.Factorization.FiniteField Methods sqfree :: UPolynomial (PrimeField p) -> [(UPolynomial (PrimeField p), Integer)] Source #
SQFree (UPolynomial Integer) Source #
Instance details Defined in ToySolver.Data.Polynomial.Factorization.SquareFree Methods sqfree :: UPolynomial Integer -> [(UPolynomial Integer, Integer)] Source #
(Eq k, Num k, Ord v, IsString v) => IsString (Polynomial k v) Source #
Instance details Defined in ToySolver.Data.Polynomial.Base Methods fromString :: String -> Polynomial k v #
(Eq k, Num k, Ord v) => Num (Polynomial k v) Source #
Instance details Defined in ToySolver.Data.Polynomial.Base Methods (+) :: Polynomial k v -> Polynomial k v -> Polynomial k v # (-) :: Polynomial k v -> Polynomial k v -> Polynomial k v # (*) :: Polynomial k v -> Polynomial k v -> Polynomial k v # negate :: Polynomial k v -> Polynomial k v # abs :: Polynomial k v -> Polynomial k v # signum :: Polynomial k v -> Polynomial k v # fromInteger :: Integer -> Polynomial k v #
(Show v, Show k) => Show (Polynomial k v) Source #
Instance details Defined in ToySolver.Data.Polynomial.Base Methods showsPrec :: Int -> Polynomial k v -> ShowS # show :: Polynomial k v -> String # showList :: [Polynomial k v] -> ShowS #
(NFData k, NFData v) => NFData (Polynomial k v) Source #
Instance details Defined in ToySolver.Data.Polynomial.Base Methods rnf :: Polynomial k v -> () #
(Eq v, Eq r) => Eq (Polynomial r v) Source #
Instance details Defined in ToySolver.Data.Polynomial.Base Methods (==) :: Polynomial r v -> Polynomial r v -> Bool # (/=) :: Polynomial r v -> Polynomial r v -> Bool #
(Ord v, Ord r) => Ord (Polynomial r v) Source #
Instance details Defined in ToySolver.Data.Polynomial.Base Methods compare :: Polynomial r v -> Polynomial r v -> Ordering # (<) :: Polynomial r v -> Polynomial r v -> Bool # (<=) :: Polynomial r v -> Polynomial r v -> Bool # (>) :: Polynomial r v -> Polynomial r v -> Bool # (>=) :: Polynomial r v -> Polynomial r v -> Bool # max :: Polynomial r v -> Polynomial r v -> Polynomial r v # min :: Polynomial r v -> Polynomial r v -> Polynomial r v #
(Hashable k, Hashable v) => Hashable (Polynomial k v) Source #
Instance details Defined in ToySolver.Data.Polynomial.Base Methods hashWithSalt :: Int -> Polynomial k v -> Int # hash :: Polynomial k v -> Int #
(Ord k, Num k, Ord v, PrettyCoeff k, PrettyVar v) => Pretty (Polynomial k v) Source #
Instance details Defined in ToySolver.Data.Polynomial.Base Methods pPrintPrec :: PrettyLevel -> Rational -> Polynomial k v -> Doc # pPrint :: Polynomial k v -> Doc # pPrintList :: PrettyLevel -> [Polynomial k v] -> Doc #
Degree (Polynomial k v) Source #
Instance details Defined in ToySolver.Data.Polynomial.Base Methods deg :: Polynomial k v -> Integer Source #
(Num c, Ord c, PrettyCoeff c, Ord v, PrettyVar v) => PrettyCoeff (Polynomial c v) Source #
Instance details Defined in ToySolver.Data.Polynomial.Base Methods pPrintCoeff :: PrettyLevel -> Rational -> Polynomial c v -> Doc Source # isNegativeCoeff :: Polynomial c v -> Bool Source #
(Eq k, Num k, Ord v) => AdditiveGroup (Polynomial k v) Source #
Instance details Defined in ToySolver.Data.Polynomial.Base Methods zeroV :: Polynomial k v # (^+^) :: Polynomial k v -> Polynomial k v -> Polynomial k v # negateV :: Polynomial k v -> Polynomial k v # (^-^) :: Polynomial k v -> Polynomial k v -> Polynomial k v #
(Eq k, Num k, Ord v) => VectorSpace (Polynomial k v) Source #
Instance details Defined in ToySolver.Data.Polynomial.Base Associated Types type Scalar (Polynomial k v) # Methods (*^) :: Scalar (Polynomial k v) -> Polynomial k v -> Polynomial k v #
(Eq k, Num k, Ord v) => Var (Polynomial k v) v Source #
Instance details Defined in ToySolver.Data.Polynomial.Base Methods var :: v -> Polynomial k v Source #
Ord v => Vars (Polynomial k v) v Source #
Instance details Defined in ToySolver.Data.Polynomial.Base Methods vars :: Polynomial k v -> Set v Source #
type Scalar (Polynomial k v) Source #
Instance details Defined in ToySolver.Data.Polynomial.Base type Scalar (Polynomial k v) = k

Conversion

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

Methods

var :: v -> a Source #

Instances

Instances details

Ord v => Var (Monomial v) v Source #
Instance details Defined in ToySolver.Data.Polynomial.Base Methods var :: v -> Monomial v Source #
(Eq k, Num k, Ord v) => Var (Polynomial k v) v Source #
Instance details Defined in ToySolver.Data.Polynomial.Base Methods var :: v -> Polynomial k v Source #

constant :: (Eq k, Num k) => 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

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

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

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

Instances details

Degree AReal Source #	Degree of the algebraic number. If the algebraic number's `minimalPolynomial` has degree `n`, then the algebraic number is said to be degree `n`.
Instance details Defined in ToySolver.Data.AlgebraicNumber.Real Methods deg :: AReal -> Integer Source #
Degree (Monomial v) Source #
Instance details Defined in ToySolver.Data.Polynomial.Base Methods deg :: Monomial v -> Integer Source #
Degree (Polynomial k v) Source #
Instance details Defined in ToySolver.Data.Polynomial.Base Methods deg :: Polynomial k v -> Integer Source #

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

Methods

vars :: a -> Set v Source #

Instances

Instances details

Ord v => Vars (Monomial v) v Source #
Instance details Defined in ToySolver.Data.Polynomial.Base Methods vars :: Monomial v -> Set v Source #
Ord v => Vars (Polynomial k v) v Source #
Instance details Defined in ToySolver.Data.Polynomial.Base Methods vars :: Polynomial k v -> Set v Source #

lt :: Num k => MonomialOrder v -> Polynomial k v -> Term k v Source #

leading term with respect to a given monomial order

lc :: Num k => MonomialOrder v -> Polynomial k v -> k Source #

leading coefficient with respect to a given monomial order

lm :: Num k => 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), ..].

Instances

Instances details

Factor (UPolynomial Rational) Source #
Instance details Defined in ToySolver.Data.Polynomial.Factorization.Rational Methods factor :: UPolynomial Rational -> [(UPolynomial Rational, Integer)] Source #
KnownNat p => Factor (UPolynomial (PrimeField p)) Source #
Instance details Defined in ToySolver.Data.Polynomial.Factorization.FiniteField Methods factor :: UPolynomial (PrimeField p) -> [(UPolynomial (PrimeField p), Integer)] Source #
Factor (UPolynomial Integer) Source #
Instance details Defined in ToySolver.Data.Polynomial.Factorization.Integer Methods factor :: UPolynomial Integer -> [(UPolynomial Integer, Integer)] Source #

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), ..].

Instances

Instances details

SQFree (UPolynomial Rational) Source #
Instance details Defined in ToySolver.Data.Polynomial.Factorization.SquareFree Methods sqfree :: UPolynomial Rational -> [(UPolynomial Rational, Integer)] Source #
KnownNat p => SQFree (UPolynomial (PrimeField p)) Source #
Instance details Defined in ToySolver.Data.Polynomial.Factorization.FiniteField Methods sqfree :: UPolynomial (PrimeField p) -> [(UPolynomial (PrimeField p), Integer)] Source #
SQFree (UPolynomial Integer) Source #
Instance details Defined in ToySolver.Data.Polynomial.Factorization.SquareFree Methods sqfree :: UPolynomial Integer -> [(UPolynomial Integer, Integer)] Source #

class ContPP k where Source #

Associated Types

type PPCoeff k Source #

Methods

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

Content of a polynomial

pp :: Ord v => Polynomial k v -> Polynomial (PPCoeff k) v Source #

Primitive part of a polynomial

Instances

Instances details

ContPP Integer Source #
Instance details Defined in ToySolver.Data.Polynomial.Base Associated Types type PPCoeff Integer Source # Methods cont :: Ord v => Polynomial Integer v -> Integer Source # pp :: Ord v => Polynomial Integer v -> Polynomial (PPCoeff Integer) v Source #
Integral r => ContPP (Ratio r) Source #
Instance details Defined in ToySolver.Data.Polynomial.Base Associated Types type PPCoeff (Ratio r) Source # Methods cont :: Ord v => Polynomial (Ratio r) v -> Ratio r Source # pp :: Ord v => Polynomial (Ratio r) v -> Polynomial (PPCoeff (Ratio r)) v Source #

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 => (v -> k) -> Polynomial k v -> k Source #

Evaluation

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

Substitution or bind

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

Transform polynomial coefficients.

toMonic :: (Eq r, Fractional r) => 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

data X Source #

Variable "x"

Constructors

X

Instances

Instances details

Data X Source #
Instance details Defined in ToySolver.Data.Polynomial.Base Methods gfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> X -> c X # gunfold :: (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c X # toConstr :: X -> Constr # dataTypeOf :: X -> DataType # dataCast1 :: Typeable t => (forall d. Data d => c (t d)) -> Maybe (c X) # dataCast2 :: Typeable t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c X) # gmapT :: (forall b. Data b => b -> b) -> X -> X # gmapQl :: (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> X -> r # gmapQr :: forall r r'. (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> X -> r # gmapQ :: (forall d. Data d => d -> u) -> X -> [u] # gmapQi :: Int -> (forall d. Data d => d -> u) -> X -> u # gmapM :: Monad m => (forall d. Data d => d -> m d) -> X -> m X # gmapMp :: MonadPlus m => (forall d. Data d => d -> m d) -> X -> m X # gmapMo :: MonadPlus m => (forall d. Data d => d -> m d) -> X -> m X #
Bounded X Source #
Instance details Defined in ToySolver.Data.Polynomial.Base Methods minBound :: X # maxBound :: X #
Enum X Source #
Instance details Defined in ToySolver.Data.Polynomial.Base Methods succ :: X -> X # pred :: X -> X # toEnum :: Int -> X # fromEnum :: X -> Int # enumFrom :: X -> [X] # enumFromThen :: X -> X -> [X] # enumFromTo :: X -> X -> [X] # enumFromThenTo :: X -> X -> X -> [X] #
Read X Source #
Instance details Defined in ToySolver.Data.Polynomial.Base Methods readsPrec :: Int -> ReadS X # readList :: ReadS [X] # readPrec :: ReadPrec X # readListPrec :: ReadPrec [X] #
Show X Source #
Instance details Defined in ToySolver.Data.Polynomial.Base Methods showsPrec :: Int -> X -> ShowS # show :: X -> String # showList :: [X] -> ShowS #
NFData X Source #
Instance details Defined in ToySolver.Data.Polynomial.Base Methods rnf :: X -> () #
Eq X Source #
Instance details Defined in ToySolver.Data.Polynomial.Base Methods (==) :: X -> X -> Bool # (/=) :: X -> X -> Bool #
Ord X Source #
Instance details Defined in ToySolver.Data.Polynomial.Base Methods compare :: X -> X -> Ordering # (<) :: X -> X -> Bool # (<=) :: X -> X -> Bool # (>) :: X -> X -> Bool # (>=) :: X -> X -> Bool # max :: X -> X -> X # min :: X -> X -> X #
Hashable X Source #
Instance details Defined in ToySolver.Data.Polynomial.Base Methods hashWithSalt :: Int -> X -> Int # hash :: X -> Int #
PrettyVar X Source #
Instance details Defined in ToySolver.Data.Polynomial.Base Methods pPrintVar :: PrettyLevel -> Rational -> X -> Doc Source #
Factor (UPolynomial Rational) Source #
Instance details Defined in ToySolver.Data.Polynomial.Factorization.Rational Methods factor :: UPolynomial Rational -> [(UPolynomial Rational, Integer)] Source #
KnownNat p => Factor (UPolynomial (PrimeField p)) Source #
Instance details Defined in ToySolver.Data.Polynomial.Factorization.FiniteField Methods factor :: UPolynomial (PrimeField p) -> [(UPolynomial (PrimeField p), Integer)] Source #
Factor (UPolynomial Integer) Source #
Instance details Defined in ToySolver.Data.Polynomial.Factorization.Integer Methods factor :: UPolynomial Integer -> [(UPolynomial Integer, Integer)] Source #
SQFree (UPolynomial Rational) Source #
Instance details Defined in ToySolver.Data.Polynomial.Factorization.SquareFree Methods sqfree :: UPolynomial Rational -> [(UPolynomial Rational, Integer)] Source #
KnownNat p => SQFree (UPolynomial (PrimeField p)) Source #
Instance details Defined in ToySolver.Data.Polynomial.Factorization.FiniteField Methods sqfree :: UPolynomial (PrimeField p) -> [(UPolynomial (PrimeField p), Integer)] Source #
SQFree (UPolynomial Integer) Source #
Instance details Defined in ToySolver.Data.Polynomial.Factorization.SquareFree Methods sqfree :: UPolynomial Integer -> [(UPolynomial Integer, Integer)] Source #

type UTerm k = Term k X Source #

type UMonomial = Monomial 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

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

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' :: 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.

eisensteinsCriterion :: (ContPP k, PPCoeff k ~ Integer) => UPolynomial k -> Bool Source #

Eisenstein's irreducibility criterion.

Given a polynomial with integer coefficients P[x] = an x^n + .. + a1*x + a0, it is irreducible over rational numbers if there exists a prime number p satisfying the following conditions:

p divides ai for i /= n,
p does not divides an, and
p^2 does not divides a0.

Term

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

tdeg :: Term k v -> Integer Source #

tscale :: Num k => k -> Term k v -> Term k v Source #

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

tdivides :: 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 :: (Num k, Ord v) => Term k v -> v -> Term k v Source #

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

Monic monomial

data Monomial v Source #

Monic monomials

Instances

Instances details

(Ord v, IsString v) => IsString (Monomial v) Source #
Instance details Defined in ToySolver.Data.Polynomial.Base Methods fromString :: String -> Monomial v #
Show v => Show (Monomial v) Source #
Instance details Defined in ToySolver.Data.Polynomial.Base Methods showsPrec :: Int -> Monomial v -> ShowS # show :: Monomial v -> String # showList :: [Monomial v] -> ShowS #
NFData v => NFData (Monomial v) Source #
Instance details Defined in ToySolver.Data.Polynomial.Base Methods rnf :: Monomial v -> () #
Eq v => Eq (Monomial v) Source #
Instance details Defined in ToySolver.Data.Polynomial.Base Methods (==) :: Monomial v -> Monomial v -> Bool # (/=) :: Monomial v -> Monomial v -> Bool #
Ord v => Ord (Monomial v) Source #
Instance details Defined in ToySolver.Data.Polynomial.Base Methods compare :: Monomial v -> Monomial v -> Ordering # (<) :: Monomial v -> Monomial v -> Bool # (<=) :: Monomial v -> Monomial v -> Bool # (>) :: Monomial v -> Monomial v -> Bool # (>=) :: Monomial v -> Monomial v -> Bool # max :: Monomial v -> Monomial v -> Monomial v # min :: Monomial v -> Monomial v -> Monomial v #
Hashable v => Hashable (Monomial v) Source #
Instance details Defined in ToySolver.Data.Polynomial.Base Methods hashWithSalt :: Int -> Monomial v -> Int # hash :: Monomial v -> Int #
Degree (Monomial v) Source #
Instance details Defined in ToySolver.Data.Polynomial.Base Methods deg :: Monomial v -> Integer Source #
Ord v => Var (Monomial v) v Source #
Instance details Defined in ToySolver.Data.Polynomial.Base Methods var :: v -> Monomial v Source #
Ord v => Vars (Monomial v) v Source #
Instance details Defined in ToySolver.Data.Polynomial.Base Methods vars :: Monomial v -> Set v Source #

mone :: Monomial v Source #

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

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

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

mindicesMap :: Monomial v -> Map v Integer Source #

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

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

mdivides :: Ord v => Monomial v -> Monomial v -> Bool 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 #

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

Monomial order

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

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

data PrintOptions k v Source #

Options for pretty printing polynomials

The default value can be obtained by def.

Constructors

PrintOptions
Fields pOptPrintVar :: PrettyLevel -> Rational -> v -> Doc pOptPrintCoeff :: PrettyLevel -> Rational -> k -> Doc pOptIsNegativeCoeff :: k -> Bool pOptMonomialOrder :: MonomialOrder v

Instances

Instances details

(PrettyCoeff k, PrettyVar v, Ord v) => Default (PrintOptions k v) Source #
Instance details Defined in ToySolver.Data.Polynomial.Base Methods def :: PrintOptions k v #

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

class PrettyCoeff a where Source #

Minimal complete definition

pPrintCoeff

Methods

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

isNegativeCoeff :: a -> Bool Source #

Instances

Instances details

PrettyCoeff AReal Source #
Instance details Defined in ToySolver.Data.AlgebraicNumber.Real Methods pPrintCoeff :: PrettyLevel -> Rational -> AReal -> Doc Source # isNegativeCoeff :: AReal -> Bool Source #
PrettyCoeff Integer Source #
Instance details Defined in ToySolver.Data.Polynomial.Base Methods pPrintCoeff :: PrettyLevel -> Rational -> Integer -> Doc Source # isNegativeCoeff :: Integer -> Bool Source #
(PrettyCoeff a, Integral a) => PrettyCoeff (Ratio a) Source #
Instance details Defined in ToySolver.Data.Polynomial.Base Methods pPrintCoeff :: PrettyLevel -> Rational -> Ratio a -> Doc Source # isNegativeCoeff :: Ratio a -> Bool Source #
PrettyCoeff (PrimeField a) Source #
Instance details Defined in ToySolver.Data.Polynomial.Base Methods pPrintCoeff :: PrettyLevel -> Rational -> PrimeField a -> Doc Source # isNegativeCoeff :: PrimeField a -> Bool Source #
(Num c, Ord c, PrettyCoeff c, Ord v, PrettyVar v) => PrettyCoeff (Polynomial c v) Source #
Instance details Defined in ToySolver.Data.Polynomial.Base Methods pPrintCoeff :: PrettyLevel -> Rational -> Polynomial c v -> Doc Source # isNegativeCoeff :: Polynomial c v -> Bool Source #

class PrettyVar a where Source #

Methods

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

Instances

Instances details

PrettyVar X Source #
Instance details Defined in ToySolver.Data.Polynomial.Base Methods pPrintVar :: PrettyLevel -> Rational -> X -> Doc Source #
PrettyVar Int Source #
Instance details Defined in ToySolver.Data.Polynomial.Base Methods pPrintVar :: PrettyLevel -> Rational -> Int -> Doc Source #