7
$\begingroup$

Consider the following problem:

  • Input: $n$ polynomial equations of degree $2$ in approximately $n$ variables.
  • Each equation contains about $\sqrt{n}$ monomials.
  • We would like to find one simultaneous real solution.

How large can $n$ be for today's software to solve this on a PC within reasonable time (we can define reasonable time as 24 hours).

I started to play with Matlab (MuPAD). I am using "numeric::polysysroots" and it seems that it does not return for $n=100$.

My motivation is that I'm going to have such a set of equations with $n\sim3000$. Is that hopeless?

$\endgroup$
3
  • 3
    $\begingroup$ I'm certainly not an expert here, but I'll note the following from mathworks.co.uk/help/symbolic/mupad_ref/… : "numeric::polysysroots is a hybrid routine: it calls the symbolic solver solve(eqs, vars, BackSubstitution = FALSE) and processes its symbolic result numerically." In other words, this is trying to solve the system of equations algebraically, I think, and then computing the numerical answer at the end. This technique is surely hopeless at this size, but I'd guess that genuinely numerical techniques should do fairly well. $\endgroup$ Sep 19, 2014 at 22:06
  • 6
    $\begingroup$ You asked MuPAD to return all $2^{100}$ solutions -- no wonder it doesn't work. You should probably use a Newton-Raphson-type method instead, if you only want one. I haven't run anything too similar, but my guess would be that $n=100$ is doable with it, and $n=3000$ is not completely hopeless if you can find a good starting point. $\endgroup$ Sep 19, 2014 at 22:09
  • 7
    $\begingroup$ Also, consider scicomp.stackexchange.com -- people there are much more focused on scientific computing. $\endgroup$ Sep 19, 2014 at 22:12

0

Your Answer

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