# What are the numerical methods for huge polynomial systems?

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.

• Some insights are contained in mathoverflow.net/questions/2506/…
– Avitus
Jul 27 '14 at 11:55
• @Avitus: thank you, it's interesting, but it does not answer the question about complexity and workability. Jul 27 '14 at 12:05
• @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... Jul 30 '14 at 16:23
• 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.
– Paul
Jul 30 '14 at 18:21
• Many links and some general thoughts on a related problem are contained in cs.stackexchange.com/questions/11112/… Jul 31 '14 at 7:12

## 2 Answers

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.

• Thank you! Do you think this method workable for my huge system? Jul 30 '14 at 15:53
• There's also PHCpack. (I don't know if it'll work on your system, but you can try: github.com/janverschelde/PHCpack) Jul 30 '14 at 15:58

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