multivariate polynomials

[Henning Thielemann]

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