NotAYakk 876 Report post Posted March 28, 2006 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... ;) ) 0 Share this post Link to post Share on other sites
Kambiz 758 Report post Posted March 28, 2006 I have never used it but...Maybe... GiNaC could be helpful. 0 Share this post Link to post Share on other sites
NotAYakk 876 Report post Posted March 28, 2006 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! 0 Share this post Link to post Share on other sites
lonesock 807 Report post Posted March 28, 2006 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. 0 Share this post Link to post Share on other sites
NotAYakk 876 Report post Posted March 29, 2006 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 + bandg = cX^n + d(I split them "down the middle").Thenf*g=(aX^n + b)*(cX^n+d)= acX^(2n) + (bc+ad)X^n + bdNiavely, this takes 4 multiplications of polynomials half as big.But:Let q = (a+b)(c+d)thenf*g= acX^(2n) + (bc+ad)X^n + bd= acX^(2n) + (q - ac - bd)X^n + bdwhich 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. =) 0 Share this post Link to post Share on other sites