BSD-3-Clause licensed by Andrew Lelechenko
Maintained by [email protected]
This version can be pinned in stack with:poly-0.5.0.0@sha256:e8c991d1f70a23468ca5c26e5c7747f229cd4c6fca7c6a608a231b970dde96be,2721

poly Build Status Hackage Hackage CI Stackage LTS Stackage Nightly Coverage Status

Haskell library for univariate and multivariate polynomials, backed by Vector.

> (X + 1) + (X - 1) :: VPoly Integer
2 * X + 0

> (X + 1) * (X - 1) :: UPoly Int
1 * X^2 + 0 * X + (-1)

Vectors

Poly v a is polymorphic over a container v, implementing Vector interface, and coefficients of type a. Usually v is either a boxed vector from Data.Vector or an unboxed vector from Data.Vector.Unboxed. Use unboxed vectors whenever possible, e. g., when coefficients are Int or Double.

There are handy type synonyms:

type VPoly a = Poly Data.Vector.Vector         a
type UPoly a = Poly Data.Vector.Unboxed.Vector a

Construction

The simplest way to construct a polynomial is using the pattern X:

> X^2 - 3 * X + 2 :: UPoly Int
1 * X^2 + (-3) * X + 2

(Unfortunately, types are often ambiguous and must be given explicitly.)

While being convenient to read and write in REPL, X is relatively slow. The fastest approach is to use toPoly, providing it with a vector of coefficients (constant term first):

> toPoly (Data.Vector.Unboxed.fromList [2, -3, 1 :: Int])
1 * X^2 + (-3) * X + 2

Alternatively one can enable {-# LANGUAGE OverloadedLists #-} and simply write

> [2, -3, 1] :: UPoly Int
1 * X^2 + (-3) * X + 2

There is a shortcut to construct a monomial:

> monomial 2 3.5 :: UPoly Double
3.5 * X^2 + 0.0 * X + 0.0

Operations

Most operations are provided by means of instances, like Eq and Num. For example,

> (X^2 + 1) * (X^2 - 1) :: UPoly Int
1 * X^4 + 0 * X^3 + 0 * X^2 + 0 * X + (-1)

One can also find convenient to scale by monomial (cf. monomial above):

> scale 2 3.5 (X^2 + 1) :: UPoly Double
3.5 * X^4 + 0.0 * X^3 + 3.5 * X^2 + 0.0 * X + 0.0

While Poly cannot be made an instance of Integral (because there is no meaningful toInteger), it is an instance of GcdDomain and Euclidean from semirings package. These type classes cover main functionality of Integral, providing division with remainder and gcd / lcm:

> Data.Euclidean.gcd (X^2 + 7 * X + 6) (X^2 - 5 * X - 6) :: UPoly Int
1 * X + 1

> Data.Euclidean.quotRem (X^3 + 2) (X^2 - 1 :: UPoly Double)
(1.0 * X + 0.0,1.0 * X + 2.0)

Miscellaneous utilities include eval for evaluation at a given value of indeterminate, and reciprocals deriv / integral:

> eval (X^2 + 1 :: UPoly Int) 3
10

> deriv (X^3 + 3 * X) :: UPoly Double
3.0 * X^2 + 0.0 * X + 3.0

> integral (3 * X^2 + 3) :: UPoly Double
1.0 * X^3 + 0.0 * X^2 + 3.0 * X + 0.0

Deconstruction

Use unPoly to deconstruct a polynomial to a vector of coefficients (constant term first):

> unPoly (X^2 - 3 * X + 2 :: UPoly Int)
[2,-3,1]

Further, leading is a shortcut to obtain the leading term of a non-zero polynomial, expressed as a power and a coefficient:

> leading (X^2 - 3 * X + 2 :: UPoly Double)
Just (2,1.0)

Flavours

  • Data.Poly provides dense univariate polynomials with Num-based interface. This is a default choice for most users.

  • Data.Poly.Semiring provides dense univariate polynomials with Semiring-based interface.

  • Data.Poly.Laurent provides dense univariate Laurent polynomials with Semiring-based interface.

  • Data.Poly.Sparse provides sparse univariate polynomials with Num-based interface. Besides that, you may find it easier to use in REPL because of a more readable Show instance, skipping zero coefficients.

  • Data.Poly.Sparse.Semiring provides sparse univariate polynomials with Semiring-based interface.

  • Data.Poly.Sparse.Laurent provides sparse univariate Laurent polynomials with Semiring-based interface.

  • Data.Poly.Multi provides sparse multivariate polynomials with Num-based interface.

  • Data.Poly.Multi.Semiring provides sparse multivariate polynomials with Semiring-based interface.

  • Data.Poly.Multi.Laurent provides sparse multivariate Laurent polynomials with Semiring-based interface.

All flavours are available backed by boxed or unboxed vectors.

Performance

As a rough guide, poly is at least 20x-40x faster than polynomial library. Multiplication is implemented via Karatsuba algorithm. Here is a couple of benchmarks for UPoly Int.

Benchmark polynomial, μs poly, μs speedup
addition, 100 coeffs. 45 2 22x
addition, 1000 coeffs. 441 17 25x
addition, 10000 coeffs. 6545 167 39x
multiplication, 100 coeffs. 1733 33 52x
multiplication, 1000 coeffs. 442000 1456 303x

Changes

0.5.0.0

  • Change definition of Data.Euclidean.degree to coincide with the degree of polynomial.
  • Implement multivariate polynomials (usual and Laurent).
  • Reimplement sparse univariate polynomials as a special case of multivariate ones.
  • Speed up gcd calculations for all flavours of polynomials.
  • Decomission PolyOverField: it does not improve performance any more.
  • Add function quotRemFractional.
  • Add an experimental implementation of the discrete Fourier transform.
  • Add conversion functions between dense and sparse polynomials.

0.4.0.0

  • Implement Laurent polynomials.
  • Implement orthogonal polynomials.
  • Decomission extended GCD, use Data.Euclidean.gcdExt.
  • Decomission PolyOverFractional, use PolyOverField.

0.3.3.0

  • Add function subst.
  • Fix compatibility issues.

0.3.2.0

  • Add NFData instance.
  • Implement extended GCD.
  • Rename PolyOverFractional to PolyOverField.
  • Add integral with Semiring-based interface.

0.3.1.0

  • Implement Karatsuba multiplication.
  • Add IsList instance.

0.3.0.0

  • Implement sparse polynomials.
  • Add GcdDomain and Euclidean instances.
  • Add functions leading, monomial, scale.
  • Remove function constant.

0.2.0.0

  • Fix a bug in Num.(-).
  • Add functions constant, eval, deriv, integral.
  • Add a handy pattern synonym X.

0.1.0.0

  • Initial release.