Numerical solution for a system of multivariate polynomial equations

Hi all,

I have a system of 6th-order polynomial equations in 4 variables $q_1, q_2, q_3, q_4$ (i.e. polynomials with all the terms such as $q_1^6, q_2^6, q_2^4 q_3^2$):

$P_k(q_1, q_2, q_3, q_4) = 0$ with $k=2,\dots,N$

I don't have any good guess of the q_i. So, Newton method and its variant won't work because they need a good starting point to converge to the right solution.

My question is whether exists any numerical method to find the solution of that system of equations.

Any help is greatly appreciated.

p/s: If you want to know further background information, you may want to check my previous post. Systems of polynomial equations

• What do you mean by "the right solution"? If you are saying that one of the solutions is right, and the others are wrong, what are the distinguishing features of the right one? On the other hand, if you're happy with any solution (as your remark about the univariate case suggests), what's wrong with Newton's Method, as long as it converges to some solution? – Gerry Myerson Feb 16 '11 at 4:30
• The system of polynomial equations comes from a real machine. So, if i have an exhaustive, finite number of solutions, I can test on the machine. You are right, my remark about the univariate case is wrong and misleading. So, I need either of: 1) A numerical solution for an zero-dimensional system or 2) A numerical least-square solution to an over-constrained system. – Danny Kane Feb 16 '11 at 23:37

It really depends on the kind of system you have: do you have any reasons, for instance, to believe that the number of solutions is finite?

If the system is zero-dimensional (which essentially means that you have a finite number of solutions over the complexes), then the rational univariate representation means that you can essentially reduce to the univariate case. You would still have to figure out which solution is of interest to you, but the numerical aspect is essentially the same as in the one variable case.

Now, Groebner bases are not the only tool at your disposal in this case. You might want to look at Homotopy Continuation Methods which are entirely numerical. I believe that Jan Verschelde, whose homepage I've linked to, has readily usable software from his webpage.

Good luck, and let me know how it works for you!

• Thank you for your reply. I will look into it. Yes, I believe the number of solutions is finite, given that data collected ($\mathbf{l}_i and$\mathbf{R}_i\$ in the original equations) from the manipulator moving randomly. In longer words, if the manipulator is moving in some special singular movements, then it is possible that the system is having infinite solutions. But those movements are usually special (eg., moving straight, no rotation). I believe random movements are enough to avoid those singular cases. An analytical solution may give you an description of those movements. – Danny Kane Feb 16 '11 at 4:30
• Let me second the recommendation of Verschelde's PHCpack, the "black box mode" is very easy to use. – j.c. Feb 16 '11 at 6:10
• PHCpack gives pretty good result (not perfect probably because of measurements noises). But it can give me a good prior for other method. I still have a long way to go, but there is hope. Thank you very much for your help. – Danny Kane Feb 18 '11 at 5:18
• Cool! I'm glad I could help. – Thierry Zell Feb 18 '11 at 11:46

If your polynomials have coefficients that are imperfectly measured values, then it's quite likely that that your system of equations will simply be inconsistent. In that case, you would normally be looking for a least squares solution rather than an exact solution to the system of equations. These are hard nonconvex optimization problems, so finding provably optimal solutions is impractical. In practice, heuristic global optimization methods are often useful. As another poster mentioned, homotopy methods have been popular for applications in robotics.

If you really want exact solutions to a system of polynomial equations, then Groebner basis methods are most widely used. This is implemented in computer algebra packages like Maple, Mathematica, etc. Another approach is the nullstellensatz method that has been used by De Loera et al. See

http://portal.acm.org/citation.cfm?id=1390797