4
$\begingroup$

Is there a general way to solve a multivariate polynomial (for example the one given here).

Say for instance I knew some function $F(x,y) = xy + x^2 + y^3 + 2x^2y^2 = 5$, and $G(x,y) = 7xy^2 + 4y^2x + x^2 = 7$, could I find a solution set? Is there a general method (either analytic or numeric) for solving systems such as these?

$\endgroup$

1 Answer 1

8
$\begingroup$

In short, there are two general ways to solve multivariate polynomials: 1) Groebner bases or 2) numerical algebraic geometry and homotopy continuation. The former is analytic and completely symbolic, and the latter is a numerical method. Software packages for the former include Maple and Macaulay2 and for the latter one could use HOMPACK or Phc.

The latter method is based on nothing more than transforming the solutions of a system you know how to solve to a system that you want to solve via a homotopy. If you change your example to the following:

$$F_1(x,y) = xy + x^2 + y^3 + 2x^2y^2 - 5 = 0$$ $$G_1(x,y) = 7xy^2 + 4y^2x + x^2 - 7 = 0$$

then we can use homotopy continuation to solve for this system.

The homotopy would be of the form

$$H_1(x,y; t) = (x^3 - \lambda_1)t + F_1(x,y)(1-t)$$ $$H_2(x,y; t) = (y^3 - \lambda_2)t + G_1(x,y)(1-t)$$

where $\lambda_i$ is a generic / random point in $\mathbb{C}$. Your start system would consist of the roots of $x^3 - \lambda_1$ coupled with $y^3 - \lambda_2$ (a total of 3*3 = 9 start solutions). You then track from $t = 1$ to $t = 0$ to attain the desired solutions by using a predictor (Euler, Runge-Kutta, etc.) in the $t$ variable, followed by a Multivariable Newton Correction, i.e. you start at $t = 1$, predict at some time slice $t = .95$ for each solution, and then correct back to the path to make sure your residual error for the solutions you have at $t=.95$ are within some error bound and continue until you get to $t = 0$.

$\endgroup$
2
  • 2
    $\begingroup$ How about action matrix methods where you compute a multiplication matrix and find its eigenvalues? Do you consider these as part of Grobner basis methods? $\endgroup$
    – Alex Flint
    Jul 22, 2014 at 13:37
  • $\begingroup$ You can see how often I am on math.se. But yes, you are right. This is another method. $\endgroup$ Oct 26, 2016 at 22:39

You must log in to answer this question.

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