What is a fast algorithm for finding the numerical solution of a system of N polynomial equations in three unknown variables?
I'm looking for a quick algorithm to solve a system of N polynomial equations in three unknown variables. That is, given 3 functions F0(x,y,z), F1(x,y,z)... FN(x,y,z)
, I want to find x, y, z
that F0(x,y,z) = F1(x,y,z) = ... = FN(x,y,z) = 0
.
I tried to find a solution in several different places, but I could only find very advanced papers on topics like algebraic geometry or cryptography. However, I need a simple / fast algorithm that returns a fast numerical solution. Is there such an algorithm?
source to share
Solving multiple polynomial equations in multiple variables is a difficult task. Doing this in polynomial time on average presents a Smale 17 problem. It is unlikely that you will find a quick and simple algorithm for it to actually work.
You can take a look at Cox, Little and O'Shea's Ideals, Varieties and Algorithms for an introduction to Grobner's databases. Buchberger's algorithm finds a Gröbner basis for a given polynomial ideal. You can find all solutions to a given polynomial system using the Gröbner basis for the ideal generated by polynomials, although the solution comes in a slightly awkward form.
Newton's method is the main method for solving a system of several nonlinear equations in several variables. Applied naively, Newton's method is heuristic; he will not always find a solution to the system, even if a solution exists. However, if Newton's method converges, then it converges very quickly. Thus, the task of the theory of the problem, posed by Smale, is to find a provably good initial prerequisite for starting Newton's method from.
Beltran and Pardo have made significant progress in solving Smale problem 17 by giving an algorithm that works on average for systems with limited degree using real number arithmetic. Since then, it has developed into an algorithm with finite precision by Brickwell, Cooker, Pena and Roshchina . Surprisingly, I don't know of any implementations or attempts to implement these ideas. We're still very, very far from using code to solve systems of polynomial equations.
source to share
In your last comment, you reduced your original problem to a much simpler problem, line x(t)=a+b*t
and surface intersection G(x)=0
. By simply inserting a line into a surface equation, you have a one-dimensional problem F(t)=G(a+b*t)=0
. There you can use the one-dimensional Newton method or derivative free methods like the Illinois method (regulatory falsity with swirl) or Brent's method. There is still a global problem of identifying intervals with sign reversals. There you have some idea of the shape of the surface, or you need to put a function into the table. Homotopic continuation can also play a role, since nearby lines very often have nearby roots.
source to share