[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
RE: FW: data structure vs. mathematical structure (was: [Axiom-developer
From: |
Page, Bill |
Subject: |
RE: FW: data structure vs. mathematical structure (was: [Axiom-developer] Graph theory) |
Date: |
Tue, 14 Nov 2006 17:13:34 -0500 |
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.
- [Axiom-developer] Re: FW: data structure vs. mathematical structure, (continued)
- [Axiom-developer] Re: FW: data structure vs. mathematical structure, Ralf Hemmecke, 2006/11/15
- [Axiom-developer] Re: FW: data structure vs. mathematical structure, Gabriel Dos Reis, 2006/11/15
- [Axiom-developer] Re: FW: data structure vs. mathematical structure, Ralf Hemmecke, 2006/11/15
- [Axiom-developer] Re: FW: data structure vs. mathematical structure, Gabriel Dos Reis, 2006/11/15
- [Axiom-developer] RE: FW: data structure vs. mathematical structure, Page, Bill, 2006/11/15
- [Axiom-developer] Re: FW: data structure vs. mathematical structure, Gabriel Dos Reis, 2006/11/15
- Re: [Axiom-developer] RE: FW: data structure vs. mathematical structure, Martin Rubey, 2006/11/15
- Re: FW: data structure vs. mathematical structure (was: [Axiom-developer] Graph theory), Gabriel Dos Reis, 2006/11/14
- Re: FW: data structure vs. mathematical structure (was: [Axiom-developer] Graph theory), Vanuxem GrĂ©gory, 2006/11/14