0

I have a set of quadratic equations, like 

x² + x + y = 7
x + 3y = -3
y² + x² + z = 11

All coefficients are integers. The set of equations could either have no solution, one solution of a whole set of solutions.

Does anybody know a method to find out whether these equations have a solution?

My first idea was to solve these equations one by one in double and use the results to solve the other equations. The problems are the rounding errors: If, in theory, I have two equations

x + y = 5
x = 5 - y

there would be plenty of solutions. But if my method results in

x + y = 4.999999
x = 5 - y

the system suddenly has no solution. In the next step, I could add epsilons to compensate for rounding errors, but I am not sure how large they should be. Any ideas or better approaches?

PS: The background is to find intersection points of a complicated set of circles and lines in the plane.

J Fabian Meier
  • 33,516
  • 10
  • 64
  • 142
  • 2
    You could try to use `BigDecimal` to get rid of the precision errors (you need to settle on a common maximum precision though) or compare the values with some epsilon, i.e. something like `boolean equal = Math.abs(4.999 - 5) > 0.0001;`. The latter approach is often used in geometrical applications such as collision detection etc. where results need to be numerically stable while working as low a precision as possible. – Thomas Mar 15 '17 at 15:27
  • 1
    the epsilon value is the accuracy of your intersection so in your case it is max distance of closest points on each curve/surface to be considered as intersection (the same point) usually set to a fraction of smallest detail in your shapes .... or to fraction of pixel size if rendered etc ... but beware which power of it to use ... for example if you got line `x+c0.y = c1` then you use `eps^1 ` but for circle `x^2 + y^2 = r^2` you use `eps^2` so you got still the same units / metric in between equations. I solve with [How approximation search works](http://stackoverflow.com/a/36163847/2521214) – Spektre Mar 16 '17 at 07:13

1 Answers1

1

Since you have exact input with integers you could use exact algorithms. You could, for instance, compute a Groebner basis of the polynomials corresponding to your equations, e.g.

x² + x + y - 7
x + 3y + 3
y² + x² + z - 11

With lexicographic ordering of the terms you will get a Groebner basis in a kind of "triangular" form, where the first polynomial contains as few variables as possible, e.g.

81z² - 176z + 92
2y + 9z - 8
2x - 27z + 30

This gives you two real roots for z and unique values for y and x once z is fixed. If the first polynomial of the computed basis does not contain a variable, then your set of equations does not have any solutions. If the first polynomial in the computed bases contains two variables, then you have an infinite number of solutions (possibly complex).

You can experiment with Groebner bases online with Wolfram Alpha (e.g. compute the basis for your example). A Groebner basis can be computed using the Buchberger algorithm, for which a few implementations are available in Java.

Note: the worst case complexity of the Buchberger algorithm is double exponential in the maximal total degree of the input, but in your application this might not matter.

coproc
  • 6,027
  • 2
  • 20
  • 31