Data.Poly.Multi.Semiring

Sparse multivariate polynomials with Semiring instance.

Documentation

data MultiPoly (v :: Type -> Type) (n :: Nat) (a :: Type)

Sparse polynomials of n variables with coefficients from a, backed by a Vector v (boxed, unboxed, storable, etc.).

Use patterns X, Y and Z for construction:

>>> :set -XDataKinds
>>> (X + 1) + (Y - 1) + Z :: VMultiPoly 3 Integer
1 * X + 1 * Y + 1 * Z
>>> (X + 1) * (Y - 1) :: UMultiPoly 2 Int
1 * X * Y + (-1) * X + 1 * Y + (-1)

Polynomials are stored normalized, without zero coefficients, so 0 * X + 1 equals to 1.

Ord instance does not make much sense mathematically, it is defined only for the sake of Set, Map, etc.

Instances

(Eq a, Ring a, GcdDomain a, Vector v (Vector 1 Word, a)) => GcdDomain (Poly v a)

Defined in Data.Poly.Internal.Multi.GcdDomain

Methods

divide :: Poly v a -> Poly v a -> Maybe (Poly v a)

gcd :: Poly v a -> Poly v a -> Poly v a

lcm :: Poly v a -> Poly v a -> Poly v a

coprime :: Poly v a -> Poly v a -> Bool

(Eq a, Field a, Vector v (Vector 1 Word, a)) => Euclidean (Poly v a)

Note that degree 0 = 0.

Defined in Data.Poly.Internal.Multi.Field

Methods

quotRem :: Poly v a -> Poly v a -> (Poly v a, Poly v a)

quot :: Poly v a -> Poly v a -> Poly v a

rem :: Poly v a -> Poly v a -> Poly v a

degree :: Poly v a -> Natural

(Eq a, Semiring a, Vector v (Vector n Word, a)) => IsList (MultiPoly v n a)

Defined in Data.Poly.Internal.Multi

Associated Types

type Item (MultiPoly v n a) :: Type

Methods

fromList :: [Item (MultiPoly v n a)] -> MultiPoly v n a

fromListN :: Int -> [Item (MultiPoly v n a)] -> MultiPoly v n a

toList :: MultiPoly v n a -> [Item (MultiPoly v n a)]

Eq (v (Vector n Word, a)) => Eq (MultiPoly v n a)

Defined in Data.Poly.Internal.Multi

Methods

(==) :: MultiPoly v n a -> MultiPoly v n a -> Bool

(/=) :: MultiPoly v n a -> MultiPoly v n a -> Bool

(Eq a, Num a, KnownNat n, Vector v (Vector n Word, a)) => Num (MultiPoly v n a)

Note that abs = id and signum = const 1.

Defined in Data.Poly.Internal.Multi

Methods

(+) :: MultiPoly v n a -> MultiPoly v n a -> MultiPoly v n a

(-) :: MultiPoly v n a -> MultiPoly v n a -> MultiPoly v n a

(*) :: MultiPoly v n a -> MultiPoly v n a -> MultiPoly v n a

negate :: MultiPoly v n a -> MultiPoly v n a

abs :: MultiPoly v n a -> MultiPoly v n a

signum :: MultiPoly v n a -> MultiPoly v n a

fromInteger :: Integer -> MultiPoly v n a

Ord (v (Vector n Word, a)) => Ord (MultiPoly v n a)

Defined in Data.Poly.Internal.Multi

Methods

compare :: MultiPoly v n a -> MultiPoly v n a -> Ordering

(<) :: MultiPoly v n a -> MultiPoly v n a -> Bool

(<=) :: MultiPoly v n a -> MultiPoly v n a -> Bool

(>) :: MultiPoly v n a -> MultiPoly v n a -> Bool

(>=) :: MultiPoly v n a -> MultiPoly v n a -> Bool

max :: MultiPoly v n a -> MultiPoly v n a -> MultiPoly v n a

min :: MultiPoly v n a -> MultiPoly v n a -> MultiPoly v n a

(Show a, KnownNat n, Vector v (Vector n Word, a)) => Show (MultiPoly v n a)

Defined in Data.Poly.Internal.Multi

Methods

showsPrec :: Int -> MultiPoly v n a -> ShowS

show :: MultiPoly v n a -> String

showList :: [MultiPoly v n a] -> ShowS

NFData (v (Vector n Word, a)) => NFData (MultiPoly v n a)

Defined in Data.Poly.Internal.Multi

Methods

rnf :: MultiPoly v n a -> ()

(Eq a, Ring a, GcdDomain a, KnownNat n, forall (m :: Nat). KnownNat m => Vector v (Vector m Word, a), forall (m :: Nat). KnownNat m => Eq (v (Vector m Word, a))) => GcdDomain (MultiPoly v n a)

Defined in Data.Poly.Internal.Multi.GcdDomain

Methods

divide :: MultiPoly v n a -> MultiPoly v n a -> Maybe (MultiPoly v n a)

gcd :: MultiPoly v n a -> MultiPoly v n a -> MultiPoly v n a

lcm :: MultiPoly v n a -> MultiPoly v n a -> MultiPoly v n a

coprime :: MultiPoly v n a -> MultiPoly v n a -> Bool

(Eq a, Semiring a, KnownNat n, Vector v (Vector n Word, a)) => Semiring (MultiPoly v n a)

Defined in Data.Poly.Internal.Multi

Methods

plus :: MultiPoly v n a -> MultiPoly v n a -> MultiPoly v n a

zero :: MultiPoly v n a

times :: MultiPoly v n a -> MultiPoly v n a -> MultiPoly v n a

one :: MultiPoly v n a

fromNatural :: Natural -> MultiPoly v n a

(Eq a, Ring a, KnownNat n, Vector v (Vector n Word, a)) => Ring (MultiPoly v n a)

Defined in Data.Poly.Internal.Multi

Methods

negate :: MultiPoly v n a -> MultiPoly v n a

type Item (MultiPoly v n a)

Defined in Data.Poly.Internal.Multi

type Item (MultiPoly v n a) = (Vector n Word, a)

type VMultiPoly (n :: Nat) (a :: Type) = MultiPoly Vector n a

Multivariate polynomials backed by boxed vectors.

type UMultiPoly (n :: Nat) (a :: Type) = MultiPoly Vector n a

Multivariate polynomials backed by unboxed vectors.

unMultiPoly :: MultiPoly v n a -> v (Vector n Word, a)

Convert MultiPoly to a vector of (powers, coefficient) pairs.

toMultiPoly :: (Eq a, Semiring a, Vector v (Vector n Word, a)) => v (Vector n Word, a) -> MultiPoly v n a

Make MultiPoly from a list of (powers, coefficient) pairs.

>>> :set -XOverloadedLists -XDataKinds
>>> import Data.Vector.Generic.Sized (fromTuple)
>>> toMultiPoly [(fromTuple (0,0),1),(fromTuple (0,1),2),(fromTuple (1,0),3)] :: VMultiPoly 2 Integer
3 * X + 2 * Y + 1
>>> toMultiPoly [(fromTuple (0,0),0),(fromTuple (0,1),0),(fromTuple (1,0),0)] :: UMultiPoly 2 Int
0

monomial :: (Eq a, Semiring a, Vector v (Vector n Word, a)) => Vector n Word -> a -> MultiPoly v n a

Create a monomial from powers and a coefficient.

scale :: (Eq a, Semiring a, KnownNat n, Vector v (Vector n Word, a)) => Vector n Word -> a -> MultiPoly v n a -> MultiPoly v n a

Multiply a polynomial by a monomial, expressed as powers and a coefficient.

>>> :set -XDataKinds
>>> import Data.Vector.Generic.Sized (fromTuple)
>>> scale (fromTuple (1, 1)) 3 (X^2 + Y) :: UMultiPoly 2 Int
3 * X^3 * Y + 3 * X * Y^2

pattern X :: (Eq a, Semiring a, KnownNat n, 1 <= n, Vector v (Vector n Word, a)) => MultiPoly v n a

Create a polynomial equal to the first variable.

pattern Y :: (Eq a, Semiring a, KnownNat n, 2 <= n, Vector v (Vector n Word, a)) => MultiPoly v n a

Create a polynomial equal to the second variable.

pattern Z :: (Eq a, Semiring a, KnownNat n, 3 <= n, Vector v (Vector n Word, a)) => MultiPoly v n a

Create a polynomial equal to the third variable.

eval :: (Semiring a, Vector v (Vector n Word, a), Vector u a) => MultiPoly v n a -> Vector u n a -> a

Evaluate at a given point.

>>> :set -XDataKinds
>>> import Data.Vector.Generic.Sized (fromTuple)
>>> eval (X^2 + Y^2 :: UMultiPoly 2 Int) (fromTuple (3, 4) :: Data.Vector.Sized.Vector 2 Int)
25

subst :: (Eq a, Semiring a, KnownNat m, Vector v (Vector n Word, a), Vector w (Vector m Word, a)) => MultiPoly v n a -> Vector n (MultiPoly w m a) -> MultiPoly w m a

Substitute another polynomials instead of variables.

>>> :set -XDataKinds
>>> import Data.Vector.Generic.Sized (fromTuple)
>>> subst (X^2 + Y^2 + Z^2 :: UMultiPoly 3 Int) (fromTuple (X + 1, Y + 1, X + Y :: UMultiPoly 2 Int))
2 * X^2 + 2 * X * Y + 2 * X + 2 * Y^2 + 2 * Y + 2

deriv :: (Eq a, Semiring a, Vector v (Vector n Word, a)) => Finite n -> MultiPoly v n a -> MultiPoly v n a

Take a derivative with respect to the i-th variable.

>>> :set -XDataKinds
>>> deriv 0 (X^3 + 3 * Y) :: UMultiPoly 2 Int
3 * X^2
>>> deriv 1 (X^3 + 3 * Y) :: UMultiPoly 2 Int
3

integral :: (Field a, Vector v (Vector n Word, a)) => Finite n -> MultiPoly v n a -> MultiPoly v n a

Compute an indefinite integral of a polynomial by the i-th variable, setting constant term to zero.

>>> :set -XDataKinds
>>> integral 0 (3 * X^2 + 2 * Y) :: UMultiPoly 2 Double
1.0 * X^3 + 2.0 * X * Y
>>> integral 1 (3 * X^2 + 2 * Y) :: UMultiPoly 2 Double
3.0 * X^2 * Y + 1.0 * Y^2

segregate :: (Vector v (Vector (1 + m) Word, a), Vector v (Vector m Word, a)) => MultiPoly v (1 + m) a -> VPoly (MultiPoly v m a)

Interpret a multivariate polynomial over 1+m variables as a univariate polynomial, whose coefficients are multivariate polynomials over the last m variables.

unsegregate :: (Vector v (Vector (1 + m) Word, a), Vector v (Vector m Word, a)) => VPoly (MultiPoly v m a) -> MultiPoly v (1 + m) a

Interpret a univariate polynomials, whose coefficients are multivariate polynomials over the first m variables, as a multivariate polynomial over 1+m variables.