Module

# Data.Sparse.Polynomial

Package
purescript-sparse-polynomials
Repository
Ebmtranceboy/purescript-sparse-polynomials

### #PolynomialSource

``data Polynomial a``

Represents a polynomial by the discrete list of its non-zero terms, stored in a map

• from `Int` (type of the degree of a term)
• to `a` (type of the coefficient of a term: integer, real, complex, polynomic ...).
``````> -- Working with Sparse Polynomials
> import Data.Sparse.Polynomial
>
> -- Defining univariate polynomial with concatenation by (<>)
> -- of terms (monoms). Each term has the form: coef ^ degree.
> -- For instance
> 2.0 ^ 3 <> (-3.0) ^ 0
{fromTuples (Tuple 3 2.0)(Tuple 0 -3.0)}

> -- means x↦2x^3 - 3, so applied to 2:
> (2.0 ^ 3 <> (-3.0) ^ 0) :. 2.0
13.0

> -- as expected :-)
>
> -- Polynomials constitute a ring, so usual mathematical operations can
> -- be performed:
> a = 1 ^ 2 <> 4 ^ 0 -- working with Int here
> b = 1 ^ 1 <> 1 ^ 0
> a+b
{fromTuples (Tuple 2 1)(Tuple 1 1)(Tuple 0 5)}

> a-b
{fromTuples (Tuple 2 1)(Tuple 1 -1)(Tuple 0 3)}

> a*b
{fromTuples (Tuple 3 1)(Tuple 2 1)(Tuple 1 4)(Tuple 0 4)}

> -- Coefficients can be extracted:
> a ? 0
4

> --
> -- When the embedding structure is a field (Rationals, Reals,
> -- Complex ...), we can divide too
> import Data.Ratio
> r = (1%9) ^ 2 <> (2%1) ^ 0 -- meaning x↦(1/9) x^2 + 2
> s = (4%1) ^ 1 -- meaning x↦4x
> r/s
{fromTuples (Tuple 1 1 % 36)}

> r `mod` s
{fromTuples (Tuple 0 2 % 1)}

> gcd r s
fromTuples (Tuple 0 2 % 1)
>
> -- No surprise with differentiation:
> diff \$ (2%1)^3<>(-3%1)^1
{fromTuples (Tuple 2 6 % 1)(Tuple 0 -3 % 1)}

>
> -- Composition is using the (:.) apply operator:
> bThenA = (:.) b >>> (:.) a
> aThenB = (:.) a >>> (:.) b
>
> -- but this time, the application is the usual function application:
> bThenA  1
8

> aThenB 1
6

>
> -- There is also a useful tool in case of univariate real polynomials:
> pol = 1.0 ^ 2 <> 7.0 ^ 1 <> 12.0 ^ 0
> roots pol
[-2.9999999996605635-3.769201527786494e-10i,
-4.000000000339432+3.769201528752112e-10i]

> -- which gives the approximative values of all the complex roots of the
> -- polynomial.
> -- Thanks to the sparse nature of the lib, any abuse is permitted :-)
> -- but best results are given when there is no multiple roots
> roots \$ 1.0 ^ 16 <> (-1.0) ^ 0
[1.0+0.0i,0.3826834323650897+0.9238795325112867i,
-0.7071067811865476+0.7071067811865476i,
-0.9238795325112871-0.3826834323650901i,
-2.5434386919291434e-12-1.0000000000025875i,
0.9238795325108287-0.382683432364685i,
0.7071067811865476+0.7071067811865476i,
-0.9238795325112867+0.3826834323650898i,
-0.707106781186544-0.7071067811865521i,
0.382683432330398-0.9238795325016941i,
0.7071067812242033-0.7071067811940133i,
2.825247823205539e-19+1.0i,-0.3826834323650898+0.9238795325112867i,
-1.0-1.7156434035577625e-17i,-0.3826834323650554-0.9238795325112262i,
0.9238795325112867+0.3826834323650898i]

> -- To Define multivariate polynomials, it's easier with the
> -- basis 'vectors'.
> -- For instance, with 4 variables x,y,z and t, unity (=1 so
> -- not a variable!) is
> u = 1 ^ 0 ^ 0 ^ 0 ^ 0
> -- and similarly
> x = 1 ^ 1 ^ 0 ^ 0 ^ 0
> y = 1 ^ 0 ^ 1 ^ 0 ^ 0
> z = 1 ^ 0 ^ 0 ^ 1 ^ 0
> t = 1 ^ 0 ^ 0 ^ 0 ^ 1
> u
{fromTuples (Tuple 0 {fromTuples (Tuple 0 {fromTuples (Tuple 0
{fromTuples (Tuple 0 1)})})})}

> -- Setters are little more difficult.
> -- As t is the most shallow, it is the easiest
> setT val = (_ :. val)
> setZ val = (<\$>) (_ :. val)
> setY val = (<\$>) (setZ val)
> setX val = (<\$>) (setY val)
> -- but the scheme is general
> pXYZT = x + y*y + z*z*z + t*t*t*t -- meaning (x,y,z,t)↦x+y²+z³+t⁴
>
> setT 0 \$ setZ 0 \$ setY 0 \$ setX 1 pXYZT
1

> setT 0 \$ setZ 0 \$ setY 2 \$ setX 0 pXYZT
4

> setT 0 \$ setZ 3 \$ setY 0 \$ setX 0 pXYZT
27

> setT 4 \$ setZ 0 \$ setY 0 \$ setX 0 pXYZT
256

> setT 4 \$ setZ 3 \$ setY 2 \$ setX 1 pXYZT
288

> -- Coefficients can be extracted but [WARNING], in the reversed
> -- order relative to insertion
> pXYZT T ? 0 ? 0 ? 2 ? 0 -- meaning coefficient of y²
1

``````

#### Constructors

• `Poly (Map Int a)`

#### Instances

• `Semigroup (Polynomial a)`

Warning : the 2 appended maps are assumed without common keys and when they aren't, `<>` is used as the operator of resetting the argument to its right by the argument to its left

• `(Eq a) => Eq (Polynomial a)`
• `Functor Polynomial`
• `(Eq a, Semiring a) => Semiring (Polynomial a)`
• `(Eq a, Semiring a, Ring a) => Ring (Polynomial a)`
• `(Eq a, CommutativeRing a) => CommutativeRing (Polynomial a)`
• `(Eq a, DivisionRing a, CommutativeRing a) => EuclideanRing (Polynomial a)`

Warning : prelude's gcd will not work as the condition degree = 0 is not sufficient to stop the recursion asking for value = 0

• `(Ord a, Eq a, CommutativeRing a) => Ord (Polynomial a)`
• `(Show a) => Show (Polynomial a)`

### #IntLiftableSource

``class IntLiftable a  where``

#### Members

• `fromInt :: Int -> a`

#### Instances

• `IntLiftable Int`
• `IntLiftable Number`
• `(Semiring a, Ring a, IntLiftable a) => IntLiftable (Cartesian a)`
• `(Ord a, IntLiftable a, EuclideanRing a) => IntLiftable (Ratio a)`

### #applyPolySource

``applyPoly :: forall a. Semiring a => Polynomial a -> a -> a``

Polynomial application

### #bezoutSource

``bezout :: forall a. Eq a => CommutativeRing a => DivisionRing a => Polynomial a -> Polynomial a -> { u :: Polynomial a, v :: Polynomial a }``

Find 2 polynomials u and v such that u p1 + v p2 == gcd (p1,p2)

### #derivativeSource

``derivative :: forall a. Eq a => Semiring a => (Int -> a) -> Polynomial a -> Polynomial a``

### #diffSource

``diff :: forall a. Eq a => Ord a => Semiring a => EuclideanRing a => IntLiftable a => Polynomial a -> Polynomial a``

Univariate polynomial differentiation

### #dominantMonomSource

``dominantMonom :: forall a. Eq a => Semiring a => Polynomial a -> Tuple Int a``

### #gcdSource

``gcd :: forall a. Eq a => DivisionRing a => CommutativeRing a => Polynomial a -> Polynomial a -> Polynomial a``

Greatest common divisor of 2 univariate polynomials

### #liftCSource

``liftC :: Polynomial Number -> Polynomial (Cartesian Number)``

Transforms a polynomial with real arguments into a polynomial with complex arguments

### #monoPolSource

``monoPol :: forall a. a -> Int -> Polynomial a``

Monoterm polynomial

### #powSource

``pow :: forall a. Semiring a => a -> Int -> a``

Integer power

### #querySource

``query :: forall a. Semiring a => Polynomial a -> Int -> a``

Coefficient extraction

### #rootsSource

``roots :: Polynomial Number -> Array (Cartesian Number)``

Returns the n approximative roots of a polynomial of degree n

### #sortedMonomsSource

``sortedMonoms :: forall a. Polynomial a -> Array (Tuple Int a)``

Dispatches the terms in list of tuples (degree,coefficient) and order it by decreasing degree

### #(:.)Source

Operator alias for Data.Sparse.Polynomial.applyPoly (left-associative / precedence 5)

Polynomial application infix notation

### #(?)Source

Operator alias for Data.Sparse.Polynomial.query (left-associative / precedence 8)

Coefficient extraction infix notation

### #(^)Source

Operator alias for Data.Sparse.Polynomial.monoPol (left-associative / precedence 8)

Monoterm polynomial infix notation