1
$\begingroup$

I have 5 polynomial equations for 5 variables and I know that the set of roots is finite. All coefficients are integers. Ultimately I'd like to find all roots but finding the Groebner basis is impossible it seems (I tried maple, mathematica, sympy) probably because it takes too long or too much memory. But I found a rather simple root just by looking at the equations :) Now I'd like to use the fact that 1 root is known to somehow reduce the set of polynomials to lower order ones, if possible, in order to simplify the problem. How would I go about this?

$\endgroup$
  • $\begingroup$ Why do you think you need to find a Groebner basis to find the roots? $\endgroup$ – Somos Dec 11 '18 at 23:14
  • $\begingroup$ @Somos, Gröbner bases computations is one of the main tools for finding polynomial gcd's and thus solving systems of multivariate polynomial equations. $\endgroup$ – Konstantinos Kanakoglou Dec 12 '18 at 1:27
  • $\begingroup$ "One of" but not the only tool. Have you tried resultants? Also, have you tried to substitute the one known root into the five eqatuions? $\endgroup$ – Somos Dec 12 '18 at 1:30
  • $\begingroup$ is computing the resultant more efficient (from the computational viewpoint) than computing the Gröbner basis? $\endgroup$ – Konstantinos Kanakoglou Dec 12 '18 at 1:33
  • $\begingroup$ Software you listed is not know for having very good Grobner bases implementations. $\endgroup$ – Dima Pasechnik Dec 12 '18 at 5:29
4
$\begingroup$

If $p = (a_1,\dotsc,a_n)$ is a known solution and your system of equations is given by the ideal $I$, then a system of equations for all the other solutions is given as follows. Let $m_p = (x_1-a_1,\dotsc,x_n-a_n)$ be the maximal ideal corresponding to $p$. Then the saturation $I:m_p^\infty$ given by $$ I:m_p^{\infty} = \{ f : \exists n, f m_p^n \subseteq I \} $$ is an ideal whose solutions (vanishing points) are precisely the solutions of $I$ other than $p$. This is under the assumption that $p$ is an isolated solution of $I$, which is the case since you know $I$ has finitely many solutions. See https://en.wikipedia.org/wiki/Ideal_quotient.

The saturation can be computed by Gröbner basis methods. For example, Macaulay2 has a command to compute the saturation. Just a guess here, but my feeling is that the saturation is easier to compute than finding the solutions other than $p$; now, whether $I:m_p^{\infty}$ is easier to solve, enough to justify that extra saturation computation, is more of a question. It probably depends on your particular ideal.

Perhaps a better approach is via numerical algebraic geometry, represented by software such as Bertini, PHCpack, etc. These software packages are exactly designed to find solutions of polynomial systems like yours. Your system is square (5 variables, 5 equations) and has finitely many solutions. If you're okay with numerical solutions, then Bertini or one of the others might be able to solve it for you. If you need "exact" solutions, then with the numerical solutions in hand, you could try something like LLL to recover "exact" solutions.

$\endgroup$
  • 3
    $\begingroup$ In the end Bertini proved the most useful, it could find numerically all the roots of the original set of polynomials (including the analytically known one as well). It definitely beats maple/mathematica/sympy in this class of problems. $\endgroup$ – DanielFetchinson Dec 12 '18 at 10:39

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.