Polynomial Library

I have never used it but...
Maybe... GiNaC could be helpful.

Ayep, that is the kind of thing I was looking for.

I do have to check performance on large-polynomial-multiplication (they are using fast large-interger multiplication, so there is some hope), but it looks like a very pretty library.

Thanks!

I have a simple polynomial library I wrote a while back...the multiplication is the naive O(m*n), but auto collates(sp?) each "node" as it is generated, so the memory requirements don't scale by m*n (memory allocation was the bottleneck for my code). If you would like to try it feel free to PM me with an email address and I'll send it over.

I have that. =)

I can't see any indication that the above library has better-than-O(nm) polynomial multiplication, sadly.

In any case, my polynomials are very sparse on the ground, so when I multiply two terms together I end up with almost n*m terms. ;)

I currently use a map, and I'm not very optimal about throw-away polynomials. Given how I'm using the library, I'm going to replace my std::map with vector-based QuickMap (which sorts on read, appends on write) optimized for duplication, allocation, deallocation and phases of mass insert followed by phases of mass reading.

My analysis is too rusty to implement fourier polynomial multiplication, but I can manage a faster multiplication (if I can get it to deal with sparse polynomials well).

Let f and g be two polynomials of degree at most 2n.

Then for some a, b, c and d polynomials of degree less than n,
f = aX^n + b
and
g = cX^n + d

(I split them "down the middle").

Then
f*g
=(aX^n + b)*(cX^n+d)
= acX^(2n) + (bc+ad)X^n + bd

Niavely, this takes 4 multiplications of polynomials half as big.

But:
Let q = (a+b)(c+d)
then
f*g
= acX^(2n) + (bc+ad)X^n + bd
= acX^(2n) + (q - ac - bd)X^n + bd
which only takes 3 multiplications of polynomials of degree n or less to multiply two polynomials of degree 2n.

The result is an O(n^lg(3)) algorithm.

Haven't gotten around to either impplmenting it or trying out the GiNaC library -- life gets busy. =)