Speed comparison to Mathematica

[saad khalid]

Hey guys:

I wasn't sure where to ask this, so I thought I'd put it here. I've got a fairly long algorithm that I've written in Mathematica. I was wondering, do you think there would be a speed increase if I were to program it into Sage? What are some tips for a speed increase? I was thinking that I would use lambda notation to define the function, like it says here
http://ask.sagemath.org/question/8027/how-to-sum/

However, what are other things? And do you think it would actually be worthwhile? It's an algorhythm for calculating groebner bases. I don't know if that matter. I just didn't know if the language would give any sizable increase in speed. Thanks!

[William Stein]

It is impossible to answer this question if you don't provide your
code. With your complete code and exactly the
inputs (or range of inputs) that you care about, it would then only be
extremely challenging to answer your question...

William


--
William (http://wstein.org)

[john_perry_usm]

On Friday, April 29, 2016 at 1:07:31 PM UTC-5, saad khalid wrote:

However, what are other things? And do you think it would actually be worthwhile? It's an algorhythm for calculating groebner bases. I don't know if that matter. I just didn't know if the language would give any sizable increase in speed. Thanks!

For the sake of argument, let's assume that Sage does give you an increase in speed. Whether it's worthwhile depends on the novelty of the algorithm and whether you want that increase in speed in order to study it or in order to set records:

If you want speed to study it, implementing it yourself in Sage is (IMHO) a good idea because Sage has fairly good debugging facilities like a trace function, and you can compile parts of it via Cython. I did this for an algorithm I published a paper on a couple of years ago; it wasn't the speed that got the paper published so much as the novelty of the algorithm and my ability to document certain structural issues. I'm 99% certain it would have been much harder to do that in Mathematica or Maple (which I once used) or other CAS's that use a non-standard programming language as their interface.

On the other hand, setting records is unlikely, unless you're very dedicated and plan to spend a lot of time and energy on it. Caboara has said that implementing an algorithm to compute Groebner bases doesn't take a lot of effort or time, but neither will it perform well. One then has to spend the next several years (!!!) optimizing the implementation. Similarly, Faugere has said that he spent at least five years working on the F5 algorithm, for similar reasons. I know Christian Eder spent a long time years implementing an F5-like algorithm in the Singular kernel, though to be honest I don't remember exactly how long, but he documented parts of the theoretical process in papers published over 2-3 years. (The algorithm is called dstd().)

I know at least two people who worked on Groebner basis implementations and ended up leaving the CAS community to make more money in private industry. I know one of them was at least partly discouraged by how difficult it was to build an efficient implementation.

One reason for the difficulty is that a lot of small optimizations in most implementations aren't documented anywhere, neither in publications nor in the code themselves, and the contribute an enormous amount of the speedup. Some of the standard algorithms published in textbooks actually give the wrong advice; the Becker-Weispfenning text, for instance, tells you to discard redundant polynomials from the ideal. (That may not be 100% true, but it's certainly how I understood it. They certainly imply it, and don't tell you otherwise.) But that's actually a bad idea, because the redundant polynomials are typically sparser than the polynomials you'd use to replace them, and dense polynomials seem to make reduction much more time-consuming (for hopefully obvious reasons).

I would suggest that you use Sage, but rather than doing it for speed, do it to get a foot in the door with Sage development & the open-source mindset. As you work more and more in Sage, you can dig into the details of how Sage implements things, and that can give you ideas how either to modify Singular (the engine Sage uses for Groebner bases) or how to build your own implementation later (typically unwise).

[john_perry_usm]

If you want speed to study it, implementing it yourself in Sage is (IMHO) a good idea because Sage has fairly good debugging facilities like a trace function, and you can compile parts of it via Cython.

Oops. Speaking of wrong impressions, I should qualify this statement: last I checked, you can't trace Cython code in Sage. That doesn't make it any less worthwhile: first you implement the code in Python, then you move stuff to Cython as needed.

john perry

[Ralf Stephan]

That you can't trace Cython is fortunately not true.
I do it from time to time using gdb when I trace pynac code.
Of course it's not C/Python but its cythonization, the
translated C code. The associated Cython is handily shown
in comments with the translation so you won't be lost.

[Simon King]

For Cython code in Sage, there is a %crun available that gives you some
statistics on C-functions called during a computation. It needs
gperftools being installed.

Best regards,
Simon

[john_perry_usm]

On Monday, May 2, 2016 at 1:56:55 PM UTC-5, Ralf Stephan wrote:

That you can't trace Cython is fortunately not true.
I do it from time to time using gdb when I trace pynac code.

Can you trace Cython in Sage? If so, I was genuinely unaware of that (or forgot).

[Ralf Stephan]

sage -gdb will start Sage with the ability to fall to gdb when interrupted with ctrl-c. If you have your C file handy produced from Cython you can set breakpoints there and so on.  As said it's easy to see which Cython command is represented by the C code.

--
You received this message because you are subscribed to a topic in the Google Groups "sage-support" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/sage-support/0PEjhQQ1AAE/unsubscribe.
To unsubscribe from this group and all its topics, send an email to sage-support...@googlegroups.com.
To post to this group, send email to sage-s...@googlegroups.com.
Visit this group at https://groups.google.com/group/sage-support.
For more options, visit https://groups.google.com/d/optout.

[saad khalid]

Thanks everyone for the responses. I guess I didn't know if there would be a speed difference between Cython and Mathematica the way there's a difference between C and Java(Even if it's less pronounced). I like the idea of implementing it in Sage to get a better grasp of sage/open-source development, that would be really good. On that end, would you recommend implementing it in C/python and then trying to add it as a function to Sage, or simply implement it within a sage worksheet? I've never done anything like this before, so I'm sorry if that's a rudimentary question.

[Ralf Stephan]

Even with (or especially because of) my CS background I would do it step by step.

On Wed, May 4, 2016, 03:57 saad khalid <saad...@gmail.com> wrote:

Thanks everyone for the responses. I guess I didn't know if there would be a speed difference between Cython and Mathematica the way there's a difference between C and Java(Even if it's less pronounced). I like the idea of implementing it in Sage to get a better grasp of sage/open-source development, that would be really good. On that end, would you recommend implementing it in C/python and then trying to add it as a function to Sage, or simply implement it within a sage worksheet? I've never done anything like this before, so I'm sorry if that's a rudimentary question.

--

[William Stein]

On Tuesday, May 3, 2016, saad khalid <saad...@gmail.com> wrote:

Thanks everyone for the responses. I guess I didn't know if there would be a speed difference between Cython and Mathematica the way there's a difference between C and Java(Even if it's less pronounced). I like the idea of implementing it in Sage to get a better grasp of sage/open-source development, that would be really good. On that end, would you recommend implementing it in C/python and then trying to add it as a function to Sage, or simply implement it within a sage worksheet? I've never done anything like this before, so I'm sorry if that's a rudimentary question.

I'm baffled that you continue to think you'll get any useful information without providing way more details.  

William

 

--
You received this message because you are subscribed to the Google Groups "sage-support" group.
To unsubscribe from this group and stop receiving emails from it, send an email to sage-support...@googlegroups.com.

To post to this group, send email to sage-s...@googlegroups.com.
Visit this group at https://groups.google.com/group/sage-support.
For more options, visit https://groups.google.com/d/optout.

--
Sent from my massive iPhone 6 plus.

[Simon King]

PS:

Here is an example:

On 2016-05-03, Simon King <simon...@uni-koeln.de> wrote:
> For Cython code in Sage, there is a %crun available that gives you some
> statistics on C-functions called during a computation. It needs
> gperftools being installed.

sage: M = random_matrix(GF(4,'x'), 10000,10000)
sage: %crun N=M*M
PROFILE: interrupts/evictions/bytes = 261/106/118136
Using local file /home/king/Sage/git/sage/local/bin/python.
Using local file /home/king/.sage/temp/king-C70-B/7475/tmp_eYytxx.perf.
Total: 261 samples
0 0.0% 0.0% 261 100.0% PyEval_EvalCode
0 0.0% 0.0% 261 100.0% PyEval_EvalCodeEx
0 0.0% 0.0% 261 100.0% PyEval_EvalFrameEx
0 0.0% 0.0% 261 100.0% PyNumber_Multiply
0 0.0% 0.0% 261 100.0% PyObject_Call
0 0.0% 0.0% 261 100.0% PyRun_FileExFlags
0 0.0% 0.0% 261 100.0% PyRun_SimpleFileExFlags
0 0.0% 0.0% 261 100.0% PyRun_StringFlags
0 0.0% 0.0% 261 100.0% __pyx_f_4sage_6matrix_17matrix_gf2e_dense_17Matrix_gf2e_dense__matrix_times_matrix_
...
5 1.9% 96.9% 6 2.3% _mzd_mul_naive
0 0.0% 96.9% 4 1.5% _mzed_slice2
0 0.0% 96.9% 4 1.5% mzd_mul_naive
4 1.5% 98.5% 4 1.5% word_slice_64_02 (inline)
0 0.0% 98.5% 3 1.1% _mzed_cling2
...

So, you see that it both shows you C-functions that have been obtained
from Cython code and C-functions obtained from C-libraries.

Best regards,
Simon