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

Re: Re: Solve / NSolve

• To: mathgroup at smc.vnet.net
• Subject: [mg95314] Re: [mg95296] Re: Solve / NSolve
• From: Andrzej Kozlowski <akoz at mimuw.edu.pl>
• Date: Thu, 15 Jan 2009 06:11:14 -0500 (EST)
• References: <gkgouo$3sg$1@smc.vnet.net> <200901141055.FAA18013@smc.vnet.net> <351FC0A3-BC60-4522-9D1F-5630A5073599@mimuw.edu.pl>

On 14 Jan 2009, at 17:31, Andrzej Kozlowski wrote:

>
> On 14 Jan 2009, at 11:55, Jean-Marc Gulliet wrote:
>
>>> Solve is a
>>> *symbolic* solver, i.e. it manipulates the equations in  
>>> essentially an
>>> algebraic way (which does not mean that it does so in a similar  
>>> fashion
>>> as a human being would do). OTOH, NSolve uses *numeric* algorithms.
>>> (Both sets of tools and algorithms have virtually nothing in  
>>> common in
>>> terms of strategies; roughly speaking, symbolic manipulations for  
>>> the
>>> former, iterative computations for the latter, for instance.)
>
>
> It is a common misconception  that Solve is "algenriaic" while  
> NSolve uses "iterative computations" (it generally does not,  
> FindRoot does that), or that the algorithms used by Solve and NSolve  
> have "nothing in common". Both Solve and NSolve are primarily  
> intended for solving algebraic equations. They also have quite a lot  
> in common. In fact, in when NSolve is given a non-algebraic system  
> it simply passes it to Solve and does not attempt to solve it using  
> iterative methods.  For algebraic systems both Solve and NSolve rely  
> on Groebner basis, but while Solve uses exact Groeber basis NSolve  
> (at least with WorkingPrecision other than MachiePrecision) relies  
> on Mathematica's implementation of numerical GroebnerBasis  
> (GroebnerBasis[...,CoefficientDomain->InexactNumbers]), which in  
> turns relies on Mathematica's "significance arithmetic".
> To sum up, while Solve and NSolve usually (but not always) use  
> different algorithms, they are both essentially algebraic solvers.  
> In fact NSolve is more "pure algebraic" solver since it won't even  
> touch non-algebraic equations passing them to Solve to try its luck  
> on them (which is usually lacking).
>
> Andrzej Kozlowski
>
>


I guess, the statement that NSolve "generally" does not use iterative  
methods was a bit unclear. More accurately, for a single univariate  
polynomial equations NSolve uses the Jenkins-Traub algorithm (as do  
most other CAS), which is iterative. For general polynomial systems,  
however, numerical Groebner basis is used, which ultimately leads to  
solving a univariate polynomial equation, which of course, uses an  
iterative method. So in this sense Jean-Marc was correct. However, the  
Jenkins-Traub method, even though iterative, unlike the Newton-Raphson  
method does not perform any differentiation, hence it can be  
considered "algebraic". Compare this with FindRoot, which uses the  
Newton-Raphson and works with any sufficiently smooth functions, not  
necessarily algebraic ones.

Andrzej Kozlowski