On Mon, Aug 17, 2009 at 3:51 AM, William Stein<wst...@gmail.com> wrote:
>
> 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.
Yes, I tried Mathematica couple days ago on the above examples and
it's pretty fast. But singular seems to be faster on sage.math:
In[9]:= Timing[Factor[b]]
50
Out[9]= {0.07, (x + y + z) }
sage: a = (x+y+z)**50
sage: time factor(a)
CPU times: user 0.04 s, sys: 0.00 s, total: 0.04 s
Wall time: 0.04 s
(x + y + z)^50
but one has to be fair, that mathematica converts back and forth
between the symbolic expression, while I use singular directly above
(but I think the conversion can be made negligible too with singular,
if the result is just (x + y + z)^50 ).
Is magma faster than that?
If I compare with ^30, I get in singular:
sage: a = (x+y+z)**30
sage: time factor(a)
CPU times: user 0.03 s, sys: 0.00 s, total: 0.03 s
Wall time: 0.03 s
(x + y + z)^30
and with sympy:
In [1]: a = (x+y+z)**30
In [2]: b = a.expand()
In [3]: %time factor(b, expand=False)
CPU times: user 3.02 s, sys: 0.01 s, total: 3.02 s
Wall time: 3.04 s
Out[6]:
30
(x + y + z)
so it's 100x slower, but it is pure python (it uses gmpy though), so
there is some hope with cython, we'll see.
>
> 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!
The above factorizations are not over finite fields, right?
Ondrej
--~--~---------~--~----~------------~-------~--~----~
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
-~----------~----~----~----~------~----~------~--~---
