No subject

[Lewis-Sandy, Darrell]

Henning,



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.



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?



----------------------------------------------------------------

Hi Darrell,





On Thu, 17 Jun 2010, Lewis-Sandy, Darrell wrote:



> Algorithmic efficiency arises from the appropriate choice of phi.  For

> example, polynomials rings over integers or over rationals, phi most

> efficiently should map Z->GF(p) for an appropriately chosen prime p.

> For polynomials over reals and complex numbers, the identity morphism

> is sufficient.  I am not certain that these kinds of optimizations are

> within the scope of the current optimizer, and would implement

> concrete instances such as:

>

> instance (Ord s) => UFD.C (Poly s Integer) where ... specific

> instances here

>

> instance (Ord s) => UFD.C (Poly s Double) where ... specific instances

> here

>

> Instance (Field a) => Euclidean.C (Poly () a) -- Univariate

> polynomials over fields are euclidean domains



The GHC's optimizer lets you write rewrite rules like



{-# RULES

     "intPolyGCD" gcd = intPolyGCD

   #-}



which lets GHC replace the general 'gcd' by the more specific 'intPolyGCD'

whereever types allow it. However, you cannot rely on a rewrite to be applied. Thus people often choose to use type classes for selection of appropriate algorithms.

  The optimizer approach only works, if there is a general algorithm. E.g.

recently I thought about re-arrangement of the RealField class. Functions like 'round' can be implemented very general but very slow by stupidly increasing an integer counter until it exceeds the input value. This procedure can be replaced with much more efficient routines.

  I think it is somehow consensus not to change computational complexity by an optimizer rule, thus I think also in your case a type class approach is better. In order to avoid overlapping instances special type classes as in Number.Complex are certainly the cleanest way to go.



> Where s is the type from which indeterminants of the polynomial are drawn.  This sort of instancing is not possible without flexible instancing.



You may use such a type class:



class Unit a where

    toUnit :: a -> ()



instance Unit () where

    toUnit = id





However, currently I do not understand, what this type parameter means and how () leads to univariate polynomials.



In Algebra.Algebra a Monoid type is used for representing a monomial, e.g.

   Int    - univariate polynomials, e.g. 3::Int represents x^3

   (Int,Int) - bivariate polynomials, e.g. (3,5) represents x^3 * y^5

   [Int]  - multivariate with dynamic number of variables To be more precise, you need 'newtype' wrappers around these types in order to define appropriate Monoid operations.





Regards,

Henning

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://projects.haskell.org/pipermail/numeric-prelude/attachments/20100618/6c60a8f1/attachment.htm