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

[Ralf Hemmecke]

> > > Why does Axiom have distributed and recursive polynomials. 
> > > Mathematically it's the same thing, so why bother?

> > This may not be such a good example since I think the difference
> > here is primarily related to how these domains coerce to OutputForm.

> 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.
[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