On Tue, Aug 18, 2009 at 9:13 AM, Ondrej Certik<ond...@certik.cz> wrote:
> On Mon, Aug 17, 2009 at 9:41 PM, Ondrej Certik<ond...@certik.cz> wrote:
>> On Mon, Aug 17, 2009 at 5:31 AM, William Stein<wst...@gmail.com> wrote:
>>>
>>> On Mon, Aug 17, 2009 at 3:20 AM, Ondrej Certik<ond...@certik.cz> wrote:
>>>>
>>>> On Mon, Aug 17, 2009 at 4:09 AM, Ondrej Certik<ond...@certik.cz> wrote:
>>>>> 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,
>>>
>>> Does it? Who knows what Mathematica does?
>>
>> That's right -- what I meant is that mathematica kind of hides it,
>> e.g. it behaves just like an expression, if you know what I mean. I
>> have no idea what it does below the hood.
>>
>> Many thanks for the bechmarks and the long email. I'll use it in the
>> presentation. So sympy can't yet expand and factor things like:
>>
>> (x+y)^2+1
>>
>> so for your example it only factors it to a a mul of two expressions,
>> but that's now enough. We still need to improve it.
>
> Ok, I was wrong, neither of those systems is doing it. So I tried the example:
>
> ((x+y+z)^20+1)*((x+y+z)^20+2)
>
> in sympy and it takes about 5 minutes in sympy (I didn't try the one with
> ^30).
I just try to use gmpy and now it's "only" 1m15s with sympy for the
case with ^20:
In [11]: %time c = factor(b, expand=False)
CPU times: user 75.00 s, sys: 0.08 s, total: 75.08 s
Wall time: 75.60 s
sage:
sage: %time c = factor(b)
CPU times: user 1.76 s, sys: 0.00 s, total: 1.76 s
Wall time: 1.79 s
pure singular:
sage: %time b = factor(a)
CPU times: user 1.08 s, sys: 0.00 s, total: 1.08 s
Wall time: 1.08 s
So sympy is 75x slower for this example, but given it's pure python
(+gmpy for integers), I think it's not that bad for the beginning,
we'll see what cython does with it.
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
-~----------~----~----~----~------~----~------~--~---
