How big polynomial systems can we deal with? How do you know when you don't even have to try?


Recently I tried to solve a problem posed in another MO question and ultimately I got stuck at solving system of four polynomial equations in four variables with rather large polynomials. Their degree was 16 and the number of monomial terms between 400 and 650.


Let $P(i,k,n,m)$ be the class of systems of $k$ polynomial equations in $i$ variables where the polynomials are of degree $n$ or less and have $m$ or less number of terms. And similarly let $S(i,k,n,m)$ be the subclass of polynomial system that are somehow symmetric. (I don't want to be more specific; one can take system invariant or covariant with respect to some group action or systems arising from geometrical problems where the underlying geometrical symmetry is somehow reflected in the system of equations.)

Define feasibility $F_1$ of a problem to mean that it can be solved by a current desktop computer within a week. And define feasibility $F_2$ to mean that the problem can be solved by a current faculty supercomputer within a month.


What is the current state of art of $F_1$ and $F_2$ for $P(k,n,m)$ and $S(k,n,m)$? I'm not looking for precise answer, just a rough idea about the limitations of our technology would be sufficient.

  • $\begingroup$ FYI, when I tried to compute Groenber basis (with Macaulay2) for ideals, it usually more or less stopped computing whenever it reaches my physical memory limits. I heard that it depends more on the amount of physical memory then the speed of a processor. My sample was a lot less complicated than yours. There is a google group for Macaulay2. You might want to consider posting the question there too. I was wondering in your question you are also considering the number of variables in your ambient space. $\endgroup$ – Youngsu Dec 10 '13 at 3:58
  • 1
    $\begingroup$ You seem to be asking for worst-case bounds on the run-time of Gröbner basis computations (or rather: implementations). But note that these tend to behave highly irregular / "non-continuous" -- for one input set, a Gröbner basis might be found in milliseconds, while for one with just slightly changed coefficients, the computation takes hours. I imagine this scales up. However, in practice I found that many "real-world" Gröbner basis computations are much better behaved than in the worst case. So, I wonder how meaningful any straight answer to your question would be... $\endgroup$ – Max Horn Dec 10 '13 at 8:03
  • $\begingroup$ @Youngsu: You are right, I forgot to include number of variables as a parameter. I'll edit the question accordingly. $\endgroup$ – Vít Tuček Dec 10 '13 at 13:53
  • $\begingroup$ @MaxHorn: I am aware of these irregularities. Actually, I'm more interested in the average complexity. Or rather in a more practical question "How do you know when you don't even have to try?" $\endgroup$ – Vít Tuček Dec 10 '13 at 13:55
  • $\begingroup$ Your question isn't well defined. What kind of polynomials are you interested in? $\endgroup$ – Ryan Budney Dec 10 '13 at 13:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.