RE: FW: data structure vs. mathematical structure (was: [Axiom-developer] Graph theory)

[Page, Bill]

On Tuesday, November 14, 2006 4:40 PM Ralf Hemmecke wrote:
> Cc: Bill Page; address@hidden
> Subject: Re: FW: data structure vs. mathematical structure 
> (was: [Axiom-developer] Graph theory)
> 
> >>> Why does Axiom have distributed and recursive polynomials. 
> >>> Mathematically it's the same thing, so why bother?
> >
> > Bill Page wrote:
> >> This may not be such a good example since I think the
> >> difference here is primarily related to how these domains
> >> coerce to OutputForm.
>
> Vanuxem Grégory wrote:
> > I totally disagree :-) This is a good example. I forgot where
> > and if this is the example used in the Axiom book but the 
> > authors insisted on this point. I do not think this is related
> > only to the coercion to OutputForm.

My statement about recursive polynomials in Axiom was incorrect.

> [snip]
> > I'm not a specialist of the Polynomial domains/categories in
> > Axiom (which are, I think, the most developed areas in Axiom)
> > so I can not argue about this, but some algorithms depends
> > intimately on the internal representation used.
> 
> Think of implementing Buchberger's algorithm for multivariate 
> commutative polynomial rings. In order to test whether one 
> polynomial is reducible with respect to another, one has to
> access the exponent vector of the leading term. In a distributed
> format with keeping the terms sorted LT(p) would be a O(1)
> operation. I cannot think of something of that complexity for
> recursive polynomials if the term order is chosen to be "degree
> reverse lexicographical".
>

Ralf and Greg are correct. Notice in particular the different
representations below:

Compare

http://wiki.axiom-developer.org/axiom--test--1/src/algebra/GdpolySpad

)abbrev domain GDMP GeneralDistributedMultivariatePolynomial
++ Author: Barry Trager
...
++ Description:
++   This type supports distributed multivariate polynomials
++ whose variables are from a user specified list of symbols.
++ The coefficient ring may be non commutative,
++ but the variables are assumed to commute.
++ The term ordering is specified by its third parameter.
++ Suggested types which define term orderings include: 
\spadtype{DirectProduct},
++ \spadtype{HomogeneousDirectProduct}, \spadtype{SplitHomogeneousDirectProduct}
++ and finally \spadtype{OrderedDirectProduct} which accepts an arbitrary user
++ function to define a term ordering.

GeneralDistributedMultivariatePolynomial(vl,R,E): public == private where
  vl: List Symbol
  R: Ring
  E: DirectProductCategory(#vl,NonNegativeInteger)
  OV  ==> OrderedVariableList(vl)
  SUP ==> SparseUnivariatePolynomial
  NNI ==> NonNegativeInteger

  public == PolynomialCategory(R,E,OV) with
      reorder: (%,List Integer) -> %
        ++ reorder(p, perm) applies the permutation perm to the variables
        ++ in a polynomial and returns the new correctly ordered polynomial

  private == PolynomialRing(R,E) add
    --representations
      Term := Record(k:E,c:R)
      Rep := List Term
...

and

http://wiki.axiom-developer.org/images/axiom--test--1/src/algebra/multpoly.spad.pamphlet

)abbrev domain SMP SparseMultivariatePolynomial
++ Author: Dave Barton, Barry Trager
...
++ Description:
++   This type is the basic representation of sparse recursive multivariate
++ polynomials. It is parameterized by the coefficient ring and the
++ variable set which may be infinite. The variable ordering is determined
++ by the variable set parameter. The coefficient ring may be non-commutative,
++ but the variables are assumed to commute.

SparseMultivariatePolynomial(R: Ring,VarSet: OrderedSet): C == T where
  pgcd ==> PolynomialGcdPackage(IndexedExponents VarSet,VarSet,R,%)
  C == PolynomialCategory(R,IndexedExponents(VarSet),VarSet)
  SUP ==> SparseUnivariatePolynomial
  T == add
    --constants
    --D := F(%) replaced by next line until compiler support completed

    --representations
      D := SparseUnivariatePolynomial(%)
      VPoly:=  Record(v:VarSet,ts:D)
      Rep:=  Union(R,VPoly)
...

---------

Regards,
Bill Page.