Sign in to follow this  

Polynomial Library

This topic is 4278 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I'm looking for a decent C++ polynomial library (although I suppose python would be ok.) What I need: -- Can handle large sparse polynomials ---- 10,000+ coefficients with long gaps between them -- Fast multiplication (faster than naive O(n^2)). Ie, at least one of: ---- Karatsuba multiplication (or the variants on it) ---- Fourier transform multiplication ---- Other (number-theoretic?) transform-based multiplication -- Substitution of variables (x for x^500) -- Derivative/evaluate/etc Ideally, but I can deal with it if it can't: -- C++ esque (with overloaded operators, etc) -- Understands multi-variable polynomials -- Serialization/deserialization -- "Fast return" classes or "Copy on write" or the like I'm about half way there with self-written library, and ran into a problem with the speed of multiplication (a test case took more than an hour to multiply). At this point, I can either continue improving my own implementation, or find one that already has fast multiplication. =) Does anyone have any recommended libraries? (And no, I don't expect to be able to multiply two 100,000 element polynomials in real time. But less than 10 minutes would be nice... ;) )

Share this post


Link to post
Share on other sites
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!

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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. =)

Share this post


Link to post
Share on other sites

This topic is 4278 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this