4
$\begingroup$

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

Improve this question
$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$
    – Gerry Myerson
    Commented Feb 16, 2011 at 4:30
  • $\begingroup$ 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. $\endgroup$
    – Danny Kane
    Commented Feb 16, 2011 at 23:37

2 Answers 2

Reset to default
6
$\begingroup$

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!

Improve this answer
$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – Danny Kane
    Commented Feb 16, 2011 at 4:30
  • $\begingroup$ Let me second the recommendation of Verschelde's PHCpack, the "black box mode" is very easy to use. $\endgroup$
    – j.c.
    Commented Feb 16, 2011 at 6:10
  • $\begingroup$ 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. $\endgroup$
    – Danny Kane
    Commented Feb 18, 2011 at 5:18
  • $\begingroup$ Cool! I'm glad I could help. $\endgroup$
    – Thierry Zell
    Commented Feb 18, 2011 at 11:46
0
$\begingroup$

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

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .