Preprint on Maple's core data structure design

[Jason Moore]

Though this may be interesting to folks here:

https://peerj.com/preprints/504/

Jason
moorepants.info
+01 530-601-9791

[Ondřej Čertík]

Hi Jason,

On Mon, Mar 2, 2015 at 9:37 AM, Jason Moore <moore...@gmail.com> wrote:
> Though this may be interesting to folks here:
>
> https://peerj.com/preprints/504/

Thanks a lot for sharing it. I've added a link to the paper to our
"benchmark" issue for CSymPy:

https://github.com/sympy/csympy/issues/364

Very nice paper. This is a subsequent paper to:

Monagan, M., & Pearce, R. (2011). Sparse polynomial division using a
heap. Journal of Symbolic Computation, 46(7), 807–822.
doi:10.1016/j.jsc.2010.08.014

Anyway, to compare with Table 1., I used Piranha
(https://github.com/bluescarni/piranha). The p1 takes 0.061s (1 core)
and 0.024s (4 cores) on my computer, compared to Maple's 0.041s (1
core) and 0.013s (4 cores) from the Table 1. Francesco, the authors of
Piranha (CCed) and I are actually playing with various integer
implementations, I think there is a way to speed Piranha as well on
this benchmark.

For p2, I got 0.065s (1 core) and 0.021s (4 cores), compared Maple's
to 0.042s(1 core) and 0.017s (4 cores)

For p4, Piranha gets better.

The authors have several mistakes in specifying the polynomials in the
paragraph 5.3, but the polynomials seem correct right under the table,
judging by the number of terms, except the +1 at the end, as the
number of changes does not change if you add +1 (since there is
already a constant term) and they say that they took f1 from Fateman,
R. (2003). Comparing the speed of programs for sparse polynomial
multiplication. ACM SIGSAM Bulletin, 37(1), 4.
doi:10.1145/844076.844080, however in that article, f1 = (1+x+y+z)^20
and the benchmark is f1*(f1+1). However, Monagan uses f1 =
(1+x+y+z)^20 + 1, which gives a completely different benchmark (much
slower). It's not clear, so I am going to write to the authors about
this.

Ondrej

>
> Jason
> moorepants.info
> +01 530-601-9791
>
> --
> You received this message because you are subscribed to the Google Groups
> "sympy" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to sympy+un...@googlegroups.com.
> To post to this group, send email to sy...@googlegroups.com.
> Visit this group at http://groups.google.com/group/sympy.
> To view this discussion on the web visit
> https://groups.google.com/d/msgid/sympy/CAP7f1AjMMyP%3DdUcxGL_SS5CVDdgZgeJdcxopGZWSZFxMPWUZcA%40mail.gmail.com.
> For more options, visit https://groups.google.com/d/optout.

[Francesco Biscani]

Hello Ondrej,

sorry, I just noticed today the message (I am subscribed to the SymPy mailing list and the gmail tagging filter made this message skip my inbox).

On 2 March 2015 at 18:29, Ondřej Čertík <ondrej...@gmail.com> wrote:

Hi Jason,

On Mon, Mar 2, 2015 at 9:37 AM, Jason Moore <moore...@gmail.com> wrote:
> Though this may be interesting to folks here:
>
> https://peerj.com/preprints/504/

Thanks a lot for sharing it. I've added a link to the paper to our
"benchmark" issue for CSymPy:

https://github.com/sympy/csympy/issues/364

Very nice paper. This is a subsequent paper to:

Monagan, M., & Pearce, R. (2011). Sparse polynomial division using a
heap. Journal of Symbolic Computation, 46(7), 807–822.
doi:10.1016/j.jsc.2010.08.014

Anyway, to compare with Table 1., I used Piranha
(https://github.com/bluescarni/piranha). The p1 takes 0.061s (1 core)
and 0.024s (4 cores) on my computer, compared to Maple's 0.041s (1
core) and 0.013s (4 cores) from the Table 1. Francesco, the authors of
Piranha (CCed) and I are actually playing with various integer
implementations, I think there is a way to speed Piranha as well on
this benchmark.

For p2, I got 0.065s (1 core) and 0.021s (4 cores), compared Maple's
to 0.042s(1 core) and 0.017s (4 cores)

For p4, Piranha gets better.

Thanks for the pointer to the paper, I was not aware of it. Indeed Piranha was optimised targetting larger polynomials (~10**6 terms), so I am not too surprised that it gives better performance with larger examples.

The article does not seem to specify exactly how the integer coefficients are represented. It just mentions that only integer coefficients are supported (e.g., no rationals, floating-point, etc.). The representation of the coefficients is going to have a rather big impact on overall performance for these benchmarks (which are rather dense).

I am also quite positive we can improve Piranha's timings on smaller test cases - possibly via improvements for the integer class and the tweaking of various internal bits of the multiplication routine.

Cheers,

  Francesco.

[Ondřej Čertík]

On Thu, Mar 5, 2015 at 2:30 AM, Francesco Biscani <blues...@gmail.com> wrote:
> Hello Ondrej,
>
> sorry, I just noticed today the message (I am subscribed to the SymPy
> mailing list and the gmail tagging filter made this message skip my inbox).

No problem. I didn't know that you were subscribed.

Agreed.

Btw, I got a clarification from the author, and they benchmark the
following structure:

( (1+x+y+z)^20 + 1 ) * ( (1+x+y+z)^20 + 2 )

Which is a bit slower than the Fateman benchmark, which is just
(1+x+y+z)^20 * ( (1+x+y+z)^20 + 1 ).

Ondrej