binary tree formats in symbolic algebra ??

Probably not.
I've written "karatsuba" style polynomial arithmetic for which one could 
ordinarily
benefit from having  a representation in which it is easy to grab separately
the top and bottom  "half" a polynomial, and a linear linked list is not 
a good idea.
Copying a list into an array is not a bad idea.
People have proposed storing sparse polynomials in sparse arrays and 
hash tables
and using ordered heaps for accumulating products. Arrays are often 
quite fast.
RJF

On 3/22/2013 5:51 AM, Henry Baker wrote:
> This is a general question about symbolic algebra systems, not a question about Maxima in particular.
>
> Are there any algebra systems that utilize some sort of binary _tree_ format for symbolic expressions?
>
> For example, a univariate polynomial might be encoded in a format like this:
>
> C_i*x^2^i + D_i
>
> and C_i, D_i are both analogous expressions, e.g., C_i = C_(i-1)*x^2^(i-1) + D_(i-1).
>
> There is no change in the number of coefficients or the number of nodes, but instead of being stored in a linear list, the structure has more of a binary tree shape (nodes with zero coefficients are elided, so the tree often collapses a lot).
>
> Granted, this representation is probably only useful for really large expressions, but I would imagine that symbolic algebra systems are working on some pretty large expressions these days.
>
> If there are such systems, do you have an academic reference to a paper about such a system ?
>
> _______________________________________________
> Maxima mailing list
> Maxima at math.utexas.edu
> http://www.math.utexas.edu/mailman/listinfo/maxima