Take the 2-minute tour ×

My system of equations have both linear and non-linear equations but not quadratic or cubic or equations having variable degree more than one. example :

  x + y = 3 (linear), 
  y + z = 4 (linear), 
  x * z = 6 (non-linear), 
  x / y = 3 (non-linear), 
  y * z / x = 2 (non-linear)

There can be hundreds of equation in these system. There is no quadratic or cubic equation.

I want to know which algorithm is best for solving these system of equations and which language is better C or Matlab .

share|improve this question
I would use the linear equations to simplify the problem, and then deal with the nonlinear equations. For example, here you can replace $y$ with $3-x$ and $z$ with $1-x$, so the third equation becomes $x(1-x)=6$ (solvable). Then you can back-substitute and see if it solves the rest of your equations. –  Arturo Magidin Aug 26 '11 at 20:59
Matlab has a function fsolve for numerically solving systems of nonlinear equations. C does not. Reinventing the wheel might be a nice exercise, but for practical purposes it's usually best to use existing tools. –  Robert Israel Aug 26 '11 at 21:01
Some of these are essentially linear: for example $x/y=3$ is the same as $x-3y = 0$ (and $y\not = 0$) –  Henry Aug 26 '11 at 22:16
yz/x = 2 is of degree 2 (it is the same as x = 2yz, which has a term of degree 1 in y + degree 1 in z = total degree 2). What does it mean that there is "no quadratic or cubic equation"? Using multiple equations like x=a, y=a, z=xy one can encode quadratic and higher-degree equations such as z = a+1 instead of a^2 = a + 1. –  zyx Aug 26 '11 at 23:13
Worst comes to worst, it might be a good idea to use Gröbner bases for this... –  Ｊ. Ｍ. Aug 28 '11 at 18:18
add comment

1 Answer

In the worst case this is equivalent to solving (using real or complex numbers, to some given accuracy) an arbitrary system of nonlinear polynomial equations in many variables. Extra variables and equations of type $a = bc$ to can be used to encode $n^{\rm th}$ powers and sums of multiple terms.

Apart from the possibility of having more solutions than can be easily listed (Bezout bound on the number of solutions could be attained), basic tasks such as finding one solution, and testing whether a solution exists, are extremely difficult computational problems if you allow an arbitrary system of the given type.

One can also simulate binary constraint satisfaction problems (where every variable is 0 or 1) in this framework, so in general the problem is NP-complete or worse. I think it is strictly worse without the 0-1 constraint, and deciding existence of solutions is similar in complexity to decision problems in real-algebraic geometry where problems can be PSPACE complete or even double-exponential time for quantifier elimination.

If there is more information about the structure of the problem or what the average case looks like, the complexity could be lower in practice.

share|improve this answer
add comment

Your Answer


