On Tuesday, November 14, 2006 4:40 PM Ralf Hemmecke wrote: > Cc: Bill Page; [email protected] > 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. _______________________________________________ Axiom-developer mailing list [email protected] http://lists.nongnu.org/mailman/listinfo/axiom-developer
