Solving systems of quadratic equations

744 Views Asked by At

There are efficient algorithms for solving a system of linear equations of the form

$$\forall i \qquad 0 = a^i + \sum_j b^i_j x^j$$

or

$$\mathbf{0} = \mathbf{a} + \mathbf{b} \cdot \mathbf{x}$$

Are there efficient algorithms for solving a system of quadratic equations of the form

$$\forall i \qquad 0 = a^i + \sum_j b^i_j x^j + \sum_k \sum_j c^i_{jk} x^j x^k$$

or

$$\mathbf{0} = \mathbf{a} + \mathbf{b} \cdot \mathbf{x} + \mathbf{c} \cdot \mathbf{x} \cdot \mathbf{x}$$

and if so, what are they?

1

There are 1 best solutions below

5
On BEST ANSWER

As shown by Robert Israel's answer to a similar question, particular instances of this problem scheme need not have solutions which are simply expressed (unlike the linear case, where the solution is always expressible as finite expressions in the given coefficients, in the quadratic and higher degree cases, the solution may need roots of high degree polynomials, for which there need not be any expression in the original coefficients). So the best we can hope for is a method similar to elimination which trades fewer variables for higher degrees. Groebner basis calculations are such a method.

One might wish that the degree 2 bound in the inputs could allow a nicer solution, but no: a degree 2 bounded solution algorithm is actually an algorithm for a system with unconstrained degrees.

There are several Groebner basis implementations. I do not recommend attempting this technique by hand except for carefully constructed exercises (for which, see books, like Cox, Little, and O'Shea, Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra).