[Date Index] [Thread Index] [Author Index]

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