[NumericPrelude] multivariate polynomials

[Lewis-Sandy, Darrell]

Henning, 

In my polynomial library I did not have a function fromCoeffs because all my polynomials were multivariate.  Instead, I had a function fromTerms:

fromTerms :: (Ring a, Ord symbol) => [(ring,Bag symbol)] -> Poly symbol ring

where a term was represented as a coefficient/monomial pair, and Bag was my monoidial mononomial type.   For example, the polynomial p = x^16 - 8*x^8 + 16 could be constructed as follows:

p = fromTerms [(1,fromList [((),16)]),(-9,fromList [(),8]),(16,empty)] :: Poly () Integer

where fromList and empty represent bag constructors of the type:

fromList :: (Ord symbol) => [(symbol,Integer)]-> Bag symbol
empty    :: Bag symbol.

If I am correct, the equivalent declaration for p using the Numeric Prelude's univariate polynomial datatype would be:

p = fromCoeffs [16,0,0,0,0,0,0,0,-8,0,0,0,0,0,0,0,1] :: Polynomial.T Integer

With my sparse multivariate polynomial datatype Poly, I could declare a function for creating a univariate polynomial from a list of coefficients  assuming that the polynomial was an principal ideal domain.  It might look something like this:

fromCoeffs :: (PID.C (Poly symbol ring), Ring ring, Ord symbol) => [ring] -> Poly symbol ring
fromCoeffs xs = foldr (\c p -> constant c + p*x) z xs
    z = zero :: Poly symbol ring
    x = basis z  -- since Poly symbol ring is a PID, it has a single basis element

where basis :: (PID a) => a -> a is the class function of PID which recovers the generating element any ideal.   For sparse polynomials, the fromTerms will be more efficient since the number of additions is equal to the number of nonzero terms (compared to the degree of the polynomial), and no polynomial multiplication is required.   Best case efficiency of fromTerms would be O(n) when the terms are in strictly ascending order.  However, for explicitly univariate polynomials the Numeric prelude implementation of fromCoeffs is O(1).

What I had in mind for a class interface would provide a common interface for construction and comprehension of polynomial implementations.  For example, we might consider:

degree -- the degree of the polynomial 
degreeOf -- the degree of a specific indeterminant
terms -- list of the nonzero terms
splitleading -- split a polynomial on the leading term
variables -- list of indetermiants of the polynomial
terms -- list of non-zero terms of the polynomial
...

Such an interface might facilitate declaration of general algorithms for polynomial types;  I would be glad to put together a proposal if you think it adds value.

Darrell

 
-----Original Message-----
From: Henning Thielemann [mailto:lemming at henning-thielemann.de] 
Sent: Friday, June 18, 2010 4:48 PM
To: Lewis-Sandy, Darrell
Cc: numeric-prelude at projects.haskell.org
Subject: Re: multivariate polynomials


On Fri, 18 Jun 2010, Lewis-Sandy, Darrell wrote:

> Because in my present work I have been concerned with sparse multivariate polynomials I
> explicitly implemented my monomials as bags and the polynomials as finite mappings from
> monomials to coefficients.  When declaring the data type, one needed to specify the type
> of symbols (s) and the type of the underlying ring (a).  So in my previous mailing,
> 
>  
> 
> data Poly symbol ring
> 
>  
> 
> Represented a polynomial with symbols of type symbol and underlying ring, ring.  A
> univariate polynomial would be an instance of Poly for which s contained only a single
> symbol (e.g. ()).  Polynomials with an arbitrary dynamic number of invariants might use
> the Integer type for symbols.  I have never been satisfied with using this
> implementation for univariate or dense polynomials due to the existence of efficient
> matrix based algorithms. 


Unfortunately I still do not understand how your representation works. How 
would you define a univariate polynomial like

Poly.fromCoeffs [1,2,1]

with your Poly type?


> I like the idea of parameterizing polynomials with the monomial type because, (assuming
> that a standard monomial interface existed), one could immediately regain efficiencies
> for the univariate case.  Due to the multiple possible representations of polynomials
> (e.g. vectors, sparse trees, rational functions)  would it be worth considering going
> one step further and creating a polynomial class to provide a standard interface for
> multiple possible implementations?  

The question is, what common polynomial operations do we need, that are 
not already field operations.


Regards,
Henning