I'd like to find numerically a solution to a sparse system of 2000000 polynomial equations of degree 3 with 50000 variables and integer coefficients (or at least to decide whether or not a solution exists).

Question: Is there an algorithm and a supercomputer for which this computation is tractable today?

  • $\begingroup$ Not strictly speaking my field, but my money is on No (or maybe if you work for the NSA). $\endgroup$ – Federico Poloni Jul 29 '16 at 7:27
  • $\begingroup$ @FedericoPoloni: roughly speaking, what is your estimate for the (space and time) complexity of this computation (and for the capacity of the NSA supercomputers)? $\endgroup$ – Sebastien Palcoux Jul 29 '16 at 7:53
  • 1
    $\begingroup$ It's hard to tell. AFAIK, methods based on Gröbner bases are highly dependent on the specific structure of the equations that you are trying to solve, and the worst-case bounds are astronomically high (exponential or worse). In addition, you can construct a system of equations of the form $x_{i+1}=x_i^3$ for which the number of digits in the solution grows with the dimension, and I don't have particular reasons to believe that the decision problem is easier (apart from obvious loopholes such as "it has no solution modulo 4"). $\endgroup$ – Federico Poloni Jul 29 '16 at 8:06
  • $\begingroup$ ...and let me add that the general problem of solving diophantine equations is not even algorithmically decidable. So the best you can hope for is a ternary algorithm that returns yes/no/I don't know. $\endgroup$ – Federico Poloni Jul 29 '16 at 8:12
  • 2
    $\begingroup$ Sorry - my last remark applies only to integer solutions; I misread your question. With approximate real solutions it's a different problem. $\endgroup$ – Federico Poloni Jul 29 '16 at 9:18

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.