10
$\begingroup$

In the recent question Solving system of 7 nonlinear algebraic equations symbolically, Brian Borchers experimentally confirmed that Maple can solve a polynomial system that Matlab/Mupad cannot handle. I have heard in the past from people working in the field that Maple has a high-quality implementation of Gröbner bases and related algorithms (which I assume is what is being used here).

So I am tempted to suggest "Matlab is slow on this kind of problems, switch to Maple", but I would like to have data to back up this statement.

Is there a set of benchmark results comparing the speed and effectiveness of Gröbner basis implementations and polynomial system solutions in different computer algebra systems? (Maple, Mathematica, Matlab's symbolic toolbox, et cetera).

Improve this question
$\endgroup$
5
  • $\begingroup$ Don't forget sympy! $\endgroup$
    – Christian Clason
    Dec 30, 2015 at 10:43
  • $\begingroup$ @ChristianClason Yes, in principle there are a lot of them. Singular, Macaulay, Magma, CoCoA, Gap, Sage, Axiom, Maxima, Yacas... Do you believe that sympy is particularly good? How does it fare on Alaa's problem? $\endgroup$
    – Federico Poloni
    Dec 30, 2015 at 10:52
  • 1
    $\begingroup$ It's not that I believe it's particularly good, I'm just interested in it since it's widely available, open source, and fairly easy to learn. I tried it on the problem, but didn't get any result (but I didn't have much patience, either). $\endgroup$
    – Christian Clason
    Dec 30, 2015 at 10:58
  • $\begingroup$ I think one should differentiate between general purpose symbolic software (SymPy, Maple, Matlab's toolbox, Mathematica) and the more industrial strength, special-purpose packages (Singular, CoCoA, Macaulay). Sage is a bit different because it essentially only bundles many special-purpose packages (together with a few general-purpose ones). There's useful list on Wikipedia. $\endgroup$
    – Christian Clason
    Dec 30, 2015 at 11:05
  • $\begingroup$ Another reason I mentioned sympy is that it fills the same role Alaa is interested in -- it's easy to use the results (via lambdify) in numerical computations. $\endgroup$
    – Christian Clason
    Dec 30, 2015 at 12:30

3 Answers 3

Reset to default
12
$\begingroup$

I posted some benchmarks here: http://www.cecm.sfu.ca/~rpearcea/mgb.html (archived copy)

These are for total degree orders. To solve systems you typically need to do more work. Timings are for a typical midrange desktop as of 2015 (Haswell Core i5 quad core).

The fastest system on one core is Magma, which uses floating point arithmetic and SSE/AVX. Magma is the strongest system because it has good implementations of FGLM and the Groebner walk (not tested). These algorithms are used to convert a total degree basis to a lexicographical basis which has a triangular form. Then you would typically factor polynomials in the lowest variables.

mgb is the C library in Maple 2016 which implements the F4 algorithm for total degree and elimination orders. Its performance is comparable to Magma when it uses multiple cores.

FGb is Faugere's implementation of F4. The version tested here is from his website, and it is faster than the version in Maple.

Giac is an open source system with an implementation of F4. There is a paper describing it http://arxiv.org/abs/1309.4044

Singular is an open source system for many computations in algebraic geometry. The benchmarks here use "modStd" which is a multi-modular version of the Buchberger algorithm. You can see the Buchberger algorithm is not competitive with F4. The basic reason is that F4 amortizes the cost of all the monomial operations. Aside from that, Singular has reasonably good implementations of FGLM and the Groebner Walk, as well as other algorithms useful for solving.

Improve this answer
$\endgroup$
0
9
$\begingroup$

Googling benchmark polynomial systems leads to a few hits, including the University of Mannheim's Computer Algebra Benchmark Initiative. Sadly, most of these are out of date or defunct. The most active seems to be the SymbolicData Wiki, but as far as I can tell, it only collects benchmark problems, not benchmark results.

Some comparisons (dating back to 1996) of Axiom, Macsyma, Maple, Mathematica, MuPAD, and Reduce solving polynomial systems can be found in Hans-Gert Gräbe, About the Polynomial System Solve Facility of Axiom, Macsyma, Maple, Mathematica, MuPAD, and Reduce, Preprint 11/96 des Instituts für Informatik, Universität Leipzig, Germany, December 1996. The conclusion is that Axiom, Maple and Reduce win due to their using Gröbner bases (the others did not at this point in time), with Maple coming out slightly ahead of the others.

There's also an old comparison on the SINGULAR website showing SINGULAR 2.0 (current as of December 2015 is 4.0.2) beating Maple, among others.

On the other hand, a more recent publication (Yao Sun, Dongdai Lin, and Dingkang Wang. 2015. On implementing signature-based Gröbner basis algorithms using linear algebraic routines from M4RI. ACM Commun. Comput. Algebra 49, 2 (August 2015), 63-64 compare the authors' implementation of a Gröbner basis algorithm with that of Maple, Singular and Magma, with Magma being faster than the other two packages by an order of magnitude (and tying with the authors' implementation).

So it seems to depend very much on the problem (size as well as structure) and the software version which package is the fastest. Nevertheless, the recommendation to use an actively developed, special-purpose computer algebra system such as Singular, Magma or Maple rather than a general-purpose symbolic computation software is a sound one. This goes double for a toolbox in a numerical software, which adds another level of overhead and is usually several versions behind the stand-alone software they're based on (MuPAD, previously Maple, in the case of Matlab's toolbox).

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks for providing these resources. It is surprising to me that there are very few or no comprehensive and up-to-date benchmarks. $\endgroup$
    – Federico Poloni
    Dec 30, 2015 at 17:13
6
$\begingroup$

Always keep in mind that the results of any benchmark will depend, in addition to the problem's size, on the base field over which the polynomial ring is defined (rational numbers or integers modulo some power of a prime number).

The FGb library is an actively developed and high-performance implementation of the F5 algorithm. A benchmark comparing FGb to Magma can be found in:

Faugère, J.-C. (2010). FGb: A Library for Computing Gröbner Bases (pp. 84–87). doi:10.1007/978-3-642-15582-6_17

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.