0
$\begingroup$

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 .

  • 0
    Worst comes to worst, it might be a good idea to use Gröbner bases for this...2011-08-28

1 Answers 1

1

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.