Re: sparse polynomial arithmetic

On Apr 8, 6:45 am, bluescarni <bluesca...@xxxxxxxxx> wrote:
I'm developing a FLOSS
computer algebra system, called Piranha, geared towards Celestial
Mechanics (like TRIP, but Piranha is much more immature). Homepage is
here: http://piranha.tuxfamily.org

Here are some preliminary benchmark results (64-bit
Core2 laptop, T7100 processor, 1.8GHz, 2MB cache, 2GB RAM, GCC 4.3.0
under GNU/Linux):

Example 1: Fateman's benchmark, double-precision coefficients (16-bit
integer exponents)
f := (1+x+y+z+t)^30;
g := f+1;
multiply p := f*g;
real 0m27.953s
user 0m27.419s
sys 0m0.518s

This is much faster than Trip. That is quite impressive. Do you have
a 64-bit Linux binary I can download ? I can't install git on a 64-
bit machine.

Example 2: Fateman's benchmark, GMP mpz coefficients (16-bit integer
exponents)
f := (1+x+y+z+t)^30;
g := f+1;
multiply p := f*g;
real 6m44.520s
user 6m39.926s
sys 0m4.401s

This takes too long compared to the time for double precision.
Something is off. Are you using mpz_addmul ? You are merging
everything in a Boost hash table ? What is in the table ?

Example 5: Roman Pearce sparse benchmark, double coefficients (16-bit
integer exponents)
f := (1 + x + y + 2*z^2 + 3*t^3 + 5*u^5)^12:
g := (1 + u + t + 2*z^2 + 3*y^3 + 5*x^5)^12:
multiply p := f*g;
real 0m17.582s
user 0m15.884s
sys 0m1.684s

This is pretty good.

Example 6: Roman Pearce sparse benchmark (1 billion terms), double
coefficients (16-bit integer exponents)

NOT completed, not enough memory :/

That's too bad, but 10 variables is a lot. Try an 8 variable version:
9276 x 13073 = 2285257 terms

f := x1*x2+x1*x8+x2*x3+x3*x4+x4*x5+x5*x6+x6*x7+x7*x8
+x1+x2+x3+x4+x5+x6+x7+x8+1;
g := x1^2+x2^2+x3^2+x4^2+x5^2+x6^2+x7^2+x8^2
+x1+x2+x3+x4+x5+x6+x7+x8+1;
multiply p := f*g and divide q := p/f;

My times are 5.5 and 5.9 sec on a 2.4 GHz Core 2 Duo 6600.

Regarding the poor performance of the last two tests, I should
probably mention that memory constraints don't permit to use the
fastest algorithm

What are the different algorithms ?

Please note that Piranha is still in heavy development

Of course :) It looks like an interesting system. Thanks for showing
it.
.