Re: sparse polynomial arithmetic

On Apr 3, 11:04 pm, pari...@xxxxxxxxxxxxxx wrote:
I don't think sparness is the main problem, but memory certainly is
(512M RAM is not enough).

I disagree. Many approaches work fine on dense problems but suffer or
die on sparse problems.

You misunderstood, my point was about giac implementation. Giac
algorithm for multivariate polynomials is a mix of sparse and dense
algorithm. It is dense with respect to the first variable and sparse
with respect to other variables. For each degree of the first variable,
a thread is launched to compute the corresponding coefficient, each
coefficient being computed using sparse polynomial multiplication
(and a hash_map for sorting). Therefore giac * can benefit from
multiple processors.

Now THAT is interesting. I thought you just used one big hash table.
How well does your parallel code perform ? You really need to buy a
2.4 GHz Core2 Quad Q6600. They're cheap and the price/performance is
unbeatable. It would get you 64-bit and four cores. I would buy one
if the wife would ok a 5th computer in a one bedroom apartment :)

It's probably harder to make something similar
with heap multiplication, any idea?

Yes, but speculation isn't going to help me any, so lets save this
discussion for the future.
.