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.
> Anyway, have fun with your talk. Make sure you realize that
> factoring benchmarks depend *hugely* on the specific input and
> complexity can very a lot from run to run in Sage at least.
Yeah, all these benchmarks need to be taken with this disclaimer in
mind, but I think it's still useful, e.g. if I try several different
inputs, it gives me some feeling about the speed of all the libraries.
I hope they'll make a video of it, I'll post it to youtube or vimeo.
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
-~----------~----~----~----~------~----~------~--~---
