Re: Re: Solve / NSolve
- To: mathgroup at smc.vnet.net
- Subject: [mg95404] Re: [mg95348] Re: Solve / NSolve
- From: Andrzej Kozlowski <akoz at mimuw.edu.pl>
- Date: Sat, 17 Jan 2009 05:32:44 -0500 (EST)
- References: <gkgouo$3sg$1@smc.vnet.net> <200901161109.GAA14111@smc.vnet.net> <DBB0C883-397F-4ED4-AEA9-EC8F2DD85382@mimuw.edu.pl>
On 16 Jan 2009, at 13:25, Andrzej Kozlowski wrote: > In your second case there are no parameters and Solve and NSolve use > different algorithms. Solve rationalizes the equations and uses > exact GroebnerBasis, NSolve uses numerical Groebner basis. The first > approach is faster in this case but the second approach shoudl be > more reliable in cases involving numerical instability. I wrote the above too carelessly, so besides being vague it can be misleading. So I have decided to send a little more detailed explanation with the hope that it can be of some use. The standard method of solving systems of polynomial equations with exact coefficient is based on an algebraic algorithm called the Groebner basis algorithm. This is the algorithm used by Solve. Unfortunately, like most exact algebraic algorithms it has rather high complexity. One might hope that in cases when one only needs approximate solutions (particularly when the coefficients of the system are approximate anyway) there would be a faster numerical method. Unfortunately the GroebnerBasis algorithm is numerically unstable and in unfavorable cases a small perturbation in the coefficients of the system will lead to a very different solution. Thus the algorithm cannot be used reliably with fixed precision arithmetic (and in particular with MachinePrecision). The obvious approach, adopted by most computer algebra systems is this: given a polynomial system with inexact coefficients, first rationalize it, then use the exact Groebner basis algorithm to find solutions and finally apply N with the requested precision. This is exactly what Solve does. This method is effective except for a minor problem that rationalizing is not a unique operation so in unstable situation different rationalizations will give different results and a more serious problem that this approach will be impossibly slow on more complex systems. Mathematica offers also another approach, based on its significance arithmetic (a fast approximation to interval arithmetic) that in many situations can overcome both problems. Essentially the precision of computations is automatically increased until GroebnerBasis computations produce a stable answer. On complex problems this is usually faster than using exact Grobner basis on a rationalized system, but it can be slower in the case of simple systems. NSolve uses this approach, but I am not quite sure if it does it only when WorkingPrecision other than MachinePrecision is used or always. In any case, the general principle is: avoid if possible using symbolic functions (and that includes Simplify etc) on input containing inexact quantities as the results can be quite different form what you might expect. Andrzej Kozlowski