Ask Your Question
3

Find algebraic solutions to system of polynomial equations

asked 2014-06-12 00:53:08 -0600

MvG gravatar image

updated 2014-06-13 02:36:21 -0600

How can I find all (or all real) algebraic solutions to a set of polynomial equations, or equivalently all common roots of a set of polynomials? I'm interested in those cases where the set of solutions is finite, so the number of constraints matches the number of variables. I'm interested in exact algebraic numbers, not numeric approximations. The polynomials are elements of a polynomial ring, not symbolic expressions.

At the moment, I often use resultants to eliminate one variable after the other. In the end I have a single polynomial for one of the variables, and can find algebraic roots of that. Doing the same with a different elimination order gives candidates for the other variables, and then I can check which combinations satisfy the original equations.

But I guess there must be some more efficient approach. Probably using groebner bases. I couldn't find a simple example along these lines in the reference documentation, though.

edit retag flag offensive close merge delete

2 answers

Sort by » oldest newest most voted
2

answered 2014-06-13 01:48:47 -0600

Polynomial systems

Chapter 9 of the open-source book Calcul mathématique avec Sage (in French) is about polynomial systems. In particular, check section 9.2. The book is available for free download from: http://sagebook.gforge.inria.fr/ (click "Telecharger le PDF").

The answer below closely follows that reference, with minor adaptations in order to address the ask-sage question by MvG.

Credit goes to Marc Mezzaroba who authored that chapter, and more generally to the team who authored the book and kindly provides it under a Creative Commons license allowing all to copy and redistribute the material in any medium or format, and to remix, transform, and build upon the material, for any purpose.

The system

In section 9.2.1, the following polynomial system is considered:

$$ \left \{ \quad \begin{array}{@{}ccc@{}} x^2 \; y \; z & = & 18 \\ x \; y^3 \; z & = & 24\\ x \; y \; z^4 & = & 6 \\ \end{array}\right. $$

Numerical solve vs algebraic approach

While section 2.2 of the book explained how to solve numerically with solve,

sage: x, y, z = var('x, y, z')
sage: solve([x^2 * y * z == 18, x * y^3 * z == 24,\
....: x * y * z^4 == 3], x, y, z)
[[x == (-2.76736473308 - 1.71347969911*I), y == (-0.570103503963 +
2.00370597877*I), z == (-0.801684337646 - 0.14986077496*I)], ...]

section 9.2.1 explains how to solve algebraically.

Ideal in a polynomial ring

First translate the problem in more algebraic terms: we are looking for the common zeros of three polynomials, so we consider the polynomial ring over QQ in three variables, and in this ring we consider the ideal generated by the three polynomials whose common zeros we are looking for.

sage: R.<x,y,z> = QQ[]
sage: J = R.ideal(x^2 * y * z - 18,
....:             x * y^3 * z - 24,
....:             x * y * z^4 - 6)

We check that the dimension of this ideal is zero, which means the system has finitely many solutions.

sage: J.dimension()
0

Solution, algebraic variety, choice of base ring

The command variety will compute all the solutions of the system. However, its default behaviour is to give the solutions in the base ring of the polynomial ring. Here, this means it gives only the rational solutions.

sage: J.variety()
[{y: 2, z: 1, x: 3}]

We want to enumerate the complex solutions, as exact algebraic numbers. To do that, we use the field of algebraic numbers, QQbar. We find the 17 solutions (which were revealed by the numerical approach with solve).

sage: V = J.variety(QQbar)
sage: len(V)
17

Here is what the last three solutions look like as complex numbers.

sage: V[-3:]
[{z: 0.9324722294043558? - 0.3612416661871530?*I,
y: -1.700434271459229? + 1.052864325754712?*I,
x: 1.337215067329615? - 2.685489874065187?*I},
{z: 0.9324722294043558? + 0.3612416661871530?*I,
y: -1.700434271459229? - 1.052864325754712?*I,
x: 1.337215067329615? + 2.685489874065187?*I},
{z: 1, y: 2, x: 3}]

Each solution is given as a dictionary, whose keys are the generators of QQbar['x,y,z'] (and not QQ['x ... (more)

edit flag offensive delete link more
2

answered 2014-06-13 01:34:34 -0600

Luca gravatar image

Yes, you can use Gröbner bases. Here is an example

sage: A.<x,y,z> = QQ[]
sage: I = A.ideal(z*x^2-y, y^2-x*y, x^3+1)
sage: I.variety()
[{y: -1, z: -1, x: -1}, {y: 0, z: 0, x: -1}]

Tis is not implemented with coefficients in RR and will raise an error. However You can still ask for a Gröbner basis

sage: A.<x,y,z> = RR[]
sage: I = A.ideal(z*x^2-y, y^2-x*y, x^3+1)
sage: I.groebner_basis()
[x^3 + 1.00000000000000, x*y + z, y^2 + z, x*z - y*z, z^2 + y]
edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2014-06-12 00:53:08 -0600

Seen: 2,653 times

Last updated: Jun 13 '14