3
$\begingroup$

I have a $K$ equations of the form $x_1^{a_{i1}} \cdots x_n^{a_{in}}=c_i$ where $a_{ij}$ are non-negative integer constants and $c_i$ are real constants -- i.e. each equation is a monomial in $n$ variables and I have $k$ equations. I wish to find all real solutions for $x_1 \cdots x_n$. It is assumed that there are a finite number of real solutions.

First: is there a name for this type of problem?

Second: are there algorithms to solve this problem? Obviously I could use any polynomial system solver but I'm interested in whether there are special algorithms for this problem.

Improve this question
$\endgroup$
4
  • 3
    $\begingroup$ If $c_i$ and $x_1,\cdots,x_n$ are positive, you may use logs to reduce to the linear problem. If $x_i$ can be negative, than how you define powers $x_i^{a_i}$? $\endgroup$
    – Oleg Eroshkin
    Commented Aug 23, 2014 at 20:50
  • $\begingroup$ @OlegEroshkin My mistake, just fixed the question to specify that the $a_{ij}$ are non-negative integers, so $x_i^{a_{ij}}$ is well-defined when $x_i$ is negative. I do want to be able to find solutions when $c_i$ or $x_i$ is non-positive. $\endgroup$
    – Alex Flint
    Commented Aug 23, 2014 at 21:41
  • $\begingroup$ this is a particular case of a problem involving binomial ideals; the latter are quite well-studied, in the context of toric varieties. $\endgroup$
    – Dima Pasechnik
    Commented Aug 24, 2014 at 0:49
  • 3
    $\begingroup$ It's possible to decouple problem. Use logs to find $|x_i|$ (solving linear system over $\mathbf{R}$) and find $sign(x_i)$. Latter problem is equivalent to solving linear system over $F_2$. $\endgroup$
    – Oleg Eroshkin
    Commented Aug 24, 2014 at 2:17

2 Answers 2

Reset to default
2
$\begingroup$

As @Oleg Eroshkin has already pointed out in the comments, this is closely related to solving a linear algebraic system. You could take absolute values and then logs to obtain a linear system of the form $Ax=b$ where the entries of $x$ are absolute values of your original variables. Once you solve that, you're left with an integer programming problem for the signs.

Solving the problem in this way will also tell you qualitatively about the solution set: if $A$ is full rank, then all the solutions are identical except for changes in the signs.

Let's assume $A$ is full rank. Then equivalently, you could just apply "Gaussian elimination" directly to your system in its current form. That is, solve the first equation for $x_1$:

$$x_1 = \left(c_1 x_2^{a_{i2}} \cdots x_n^{a_{in}}\right)^{1/a_{i1}}.$$

Use this to eliminate $x_1$ from the remaining equations. Continuing in this way, you will eventually obtain an "upper triangular" system that you can solve by back substitution. You may sometimes be able to choose certain signs arbitrarily, which will again yield multiple answers.

Improve this answer
$\endgroup$
0
0
$\begingroup$

Obviously, one cannot use "any" polynomial system solver, as the latter often won't give you real solutions only.

This is a particular case of the problem of finding real roots of a binomial ideal. Binomial ideals are quite nice from the point of view of Groebner bases, as they have Groebner bases consisting of binomials, and algorithms computing these are quite efficient. Perhaps computing such a basis is a way to go for your class of problems. E.g. if you will have finitely many complex solutions, then you can find them and select the real ones among them.

Improve this answer
$\endgroup$

You must log in to answer this question.

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