On Mon, Aug 17, 2009 at 2:40 AM, Ondrej Certik<ond...@certik.cz> wrote:
>
> On Mon, Aug 17, 2009 at 2:26 AM, William Stein<wst...@gmail.com> wrote:
>>
>> On Mon, Aug 17, 2009 at 1:14 AM, Ondrej Certik<ond...@certik.cz> wrote:
>>>
>>> Hi,
>>>
>>> at the scipy 09 conference I am going to compare Sage and sympy
>>> approaches to factoring (and timings) and longer term approaches, so I
>>> have a few questions about it, so that I understand things correctly.
>>> If I do:
>>>
>>> sage: var("x y z")
>>> (x, y, z)
>>> sage: a = (x+y+z)**20
>>> sage: b = a.expand()
>>> sage: %time c = factor(b)
>>> CPU times: user 0.14 s, sys: 0.00 s, total: 0.15 s
>>> Wall time: 0.15 s
>>>
>>>
>>> 1) it uses pari, right?
>>
>> NO. Pari has no functionality at all for doing anything nontrivial
>> with multivariate polynomials. Do b.factor?? to see the source.
>> Sage tries to convert b to a poly over QQ, this works, then it calls
>> SINGULAR to factor that. If conversion doesn't work, it falls back to
>> Maxima right now.
>
> Thanks for all the clarifications, this answers all my questions. I
> was looking into the function couple days ago and I don't know how I
> got the impression that it uses pari -- when I looked now, it indeed
> uses singular and spends most of the time in the conversion.
>
> We are now roughly on the level of maxima with our new not yet
> reviewed poly patches to sympy:
>
> http://code.google.com/p/sympy/issues/detail?id=1598
>
> and with gmpy (but otherwise still pure python) it's only about 4x
> slower than sage + singular, but that's because Sage also is pure
> python here, so after cythonizing the conversion in Sage it will
> probably be 100x faster (as you suggested) --- so I am curious how
> fast sympy's factor will be after cythonizing it a bit too.
> Essentially to make fair comparisons in the long term, I'll keep in
> mind that singular is the potential top speed here (assuming you can
> optimize the conversion back and forth). You also mentioned that
> singular itself can be sped up, but I have no idea how much, as I am
> not an expert in this multivariate factoring business at all (Mateusz
> Paprocki, who wrote the sympy patches, is).
I think that if you want to get a good sense of how fast multivariate
factorization *should* be, it is valuable to benchmark Magma, Maple,
and Mathematica.
If you want some specific benchmarks for Magma, let me know and I can
compute them (if you don't have access). Maple and Mathematica are
both on sage.math, so you have access.
I have the impression that for robust fast multivariate polynomial
factorization over *finite fields* Magma is basically still the only
game in town, thanks to superb implementation work of Allen Steel
nearly a decade ago!
-- William
--~--~---------~--~----~------------~-------~--~----~
To post to this group, send an email to sage-devel@googlegroups.com
To unsubscribe from this group, send an email to
sage-devel-unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/sage-devel
URLs: http://www.sagemath.org
-~----------~----~----~----~------~----~------~--~---
