6
$\begingroup$

Let a system of $n$ polynomial equations of degree $d$ with $m$ variables.
I'm interested in a sparse system with $d = 3$, $n \sim 2000000$, $m \sim 50000$ and integer coefficients.

What techniques can I use from numerical analysis to show the existence of a solution? What numerical methods exist for finding a solution? What are the complexities? In others words, do these methods compute a solution to my problem in a reasonable time if we implement it on an efficient computer?

For more details about my system (it's a pentagon equation), see this post.

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ Some insights are contained in mathoverflow.net/questions/2506/… $\endgroup$
    – Avitus
    Jul 27 '14 at 11:55
  • $\begingroup$ @Avitus: thank you, it's interesting, but it does not answer the question about complexity and workability. $\endgroup$
    – Sebastien Palcoux
    Jul 27 '14 at 12:05
  • $\begingroup$ @Paul: Thank you for the edits. I'm interested in at least showing the existence of a solution, and finding one would be nice. Yes I've tried to use Newton's method, more precisely Gauss-Newton's method (because the Jacobian matrix is non-square), but my system seems too huge, and this method doesn't work on my desk computer. Could this method be workable on a supercomputer (or something like that)? I don't know, I'm not at all an expert... $\endgroup$
    – Sebastien Palcoux
    Jul 30 '14 at 16:23
  • $\begingroup$ Assuming a solution exists, a non-linear system of equations with approximately 50,000 unknowns is certainly within the reach of parallel computers and even some desktops. $\endgroup$
    – Paul ♦
    Jul 30 '14 at 18:21
  • $\begingroup$ Many links and some general thoughts on a related problem are contained in cs.stackexchange.com/questions/11112/… $\endgroup$
    – Thomas Klimpel
    Jul 31 '14 at 7:12
5
$\begingroup$

Certified homotopy continuation methods are used both for finding roots and for proving that they indeed exist (inside a certain interval). A quick web search turned out this paper: Reliable homotopy continuation by Joris van der Hoeven.

Improve this answer
$\endgroup$
2
4
$\begingroup$

For this kind of large scale problem, using method like Gröbner basis, or other generally used to solve polynomial system, require lots of calculation time and many times your "solution" is so big you can't do anything with it. Also to solve the system, those method required that your system is zero-dimensional which is not all the time true.

Probably a more numerical approach, may be to see this system as an non-linear equation F(x)=0, and solve it with Gauss-Newton method. As your system is big, instead of classical Newton method, check inexact Newton like Newton-Krylov. With Newton method with globalization, you have super-linear convergence.

For instance : Some explanation in : https://www10.informatik.uni-erlangen.de/de/Teaching/Courses/WS2012/SiWiR/seminar/ParPDE1.pdf and this : http://www.math.uwaterloo.ca/~tfcolema/articles/K_final_draft.pdf

Improve this answer
$\endgroup$

Your Answer

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

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