Message Boards Message Boards

GROUPS:

Theoretical questions about Solve[ ] for polynomial systems

Posted 2 months ago
476 Views
|
4 Replies
|
2 Total Likes
|

Hi there! I'm working on a project that involves solving multivariate polynomial systems of equations, and I'd like to know some details about how Solve works for a writeup if possible. Below are a few questions:

  1. Given a polynomial system, does Solve primarily use Buchberger's algorithm to generate Groebner bases for solving said system? Does this depend on whether the system is under-determined, well-determined, or over-determined?

  2. Suppose we have a well-determined complex polynomial system. When does Solve guarantee an output (i.e. a solution to the system) in theory and in practice? What if we limit the solutions to the real numbers?

  3. Does Solve ever resort to numerical/approximate methods like Newton's method? I was under the impression that NSolve was designed for that purpose, but I want to make sure I'm not leaving out part of Solve's functionality.

Links to authoritative sources would be very helpful! Thanks in advance.

4 Replies

There is a wealth of information in the tutorials accessed via Help > Wolfram Documentation. For your purposes the one below is likely to be best. As resources go, it is certainly an authority for the topic at hand.

tutorial/ComplexPolynomialSystems

Also bear in mind that Solve might perform certain "preprocessing" such as separating out linear subsystems, factoring to get disjunctions, and the like. That said, here are some specific answers.

(1) If we are solving over complexes, then a Groebner basis will be computed. This is independent of whether the system is over-, under-, or exactly-determined. Indeed, one will typically not know until such a basis has been computed.

(2) In theory, always. In practice, it is subject to limitations of computer memory, how long you might be filling to wait, and the like.

(2b) If restricting to reals, Solve might instead use methods from Real Algebraic Geometry such as Cylindrical Algebraic Geometry (CAD). This will almost certainly be the case when the system is under-determined over the complexes, since one cannot just find all finitely many solutions and discard complex-valued ones in that scenario.

(3) Solve might use validated approximation methods inside CAD, I'm not sure. It does not use Newton's method or similar. NSolve does not use them either except perhaps for root polishing (getting more correct digits from a root that was numerically approximated). If I remember correctly, this might be done in situations where the code indicates the possibility of multiplicity in the solutions.

Posted 2 months ago

Apologies--I accidentally posted my reply to you below. Thanks again for your help!

Posted 2 months ago

Thanks very much for your detailed response! It seems that the Real/Complex Polynomial Systems tutorials primarily discuss Reduce and FindInstance rather than Solve, but from what I can tell, their function is quite different (and I'd assume that their implementation is a bit different). Are there any resources detailing how Solve handles arbitrary polynomial systems?

Solve is very much like Reduce but without splitting into subcases based on parameter values. That is to say, if parameters are present they are assumed to be generic.

Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract