NSolve & PrecisionGoal

Question

I am using NSolve to find numerical solutions of a particular equation. I do not need the solutions to as high of a precision as the other numbers in my notebook. To improve run time (I am iterating this within a Table), I would like to decrease the precision, i.e., something like:

NSolve[ x^5 - 3x^4 + 3x^3 -4x^2 + 15x == 7, PrecisionGoal->3]

However, NSolve does not accept the PrecisionGoal option (nor AccuracyGoal). The similar FindRoot does; however, I would like the complete set of solutions, whereas FindRoot returns only a single solution.

NSolve does accept the somewhat related option WorkingPrecision, which determines the number of digits used in the internal calculation. Obviously, by decreasing WorkingPrecision, the resulting solutions are less precise, although there's no obvious relation between WorkingPrecision and the precision of the resulting roots (i.e., if I wanted my solutions to have a precision of 3, it's not clear what I should set the WorkingPrecision to be).

A few notes:

1) Although the example equation in the above is relatively simple, my actual equation to solve is not this simple, and so is not amenable to using Solve, although this example may be.

2) Note that I am talking specifically about NSolve; NDSolve does accept PrecisionGoal and AccuracyGoal, but I'm not solving a differential equation.

Thank you for your time.

Answer 1

Perhaps someone who knows how NSolve works will comment on my speculations or even answer. But since this question has languished, I'll share how it appears to me.

It appears to me that increasing the precision of the approximations of the roots is a minor expense relative to finding the roots. It is perhaps so minor that a PrecisionGoal option seemed pointless to the developers. There is a jump in timing when the precision reaches machine precision, but that may be because arithmetic becomes more expensive.

Indeed, the computed solutions at precisions below machine precision are identical, except that the returned solutions have different precisions. The underlying numbers appear to be the same. We can examine them by setting the precision of the solutions to infinity.

The following converts a set of approximate solutions to the (exact) rational numbers computed.

solbits[wp_: MachinePrecision] := x /. SetPrecision[
   NSolve[x^5 - 3 x^4 + 3 x^3 - 4 x^2 + 15 x == 7, x, 
    WorkingPrecision -> wp],
   Infinity]

Below I compare the numbers computed for increasing settings for WorkingPrecision. The second set of differences show the lengths of the runs of the settings for which the numbers computed for the approximate solutions are the same. The initial 15 shows that the numbers computed at working precisions below machine precision are identical.

solpos = SparseArray[
   Max /@ Abs@Differences@Table[solbits[wp], {wp, 1, 100}]
   ]["NonzeroPositions"]
Differences@Flatten[{0, solpos}]
(*
  {{15}, {16}, {19}, {20}, {21}, {22}, {31}, {32}, {33}, {38}, {39}, {41}, \
   {42}, {43}, {45}, {46}, {54}, {55}, {56}, {57}, {58}, {63}, {64}, {65}, {66}, \
   {67}, {77}, {85}, {94}, {95}, {96}}

  {15, 1, 3, 1, 1, 1, 9, 1, 1, 5, 1, 2, 1, 1, 2, 1, 8, 1, 1, 1, 1, 5, 1, 1, 1, \
   1, 10, 8, 9, 1, 1}
*)

The plot below shows that the time spent by NSolve is roughly the same for working precisions below machine precision, after which the timing rises. The timing continues to rise as working precision is increased beyond machine precision, although the rate is slow.

Needs["GeneralUtilities`"]

g[n_] := NSolve[x^15 - 3 x^4 + 3 x^3 - 4 x^2 + 15 x == 7, x, WorkingPrecision -> n];
BenchmarkPlot[{g[#] &},
 # &,
 Range[4, 24, 2],
 PlotRange -> {{3, 31}, All}]

Conclusion

I do not think you can compute all solutions faster than with MachinePrecision. The setting of WorkingPrecision seems to have an palpable effect only for settings above machine precision, something I did not appreciate before. I suspect that having a separate PrecisionGoal would not meaningfully speed up the computation, mainly because I assume once you're close to the root, a couple of iterations of Newton's method yields results accurate to machine precision. For polynomials this would not be a time-consuming calculation. But it's only a guess.

Caveat: In this exploration I looked only at univariate polynomial equations. Different types of systems probably use different algorithms, which probably have different behaviors.

Note: There is a SystemOptions[] option "NSolveOptions" -> {"Tolerance" -> 0}, but changing the setting made no difference. I do not know what the option is for.

Answer 2

Give this a try:

eq1 = x^2 + y^3 + 10 y^2 - 40 x == 1;
eq2 = 2 x + 3 y - 20 y^2 == -10;
Do[a1 = NSolve[{eq1, eq2}, {x, y}, Reals], {100}] // Timing

eq1 = SetPrecision[eq1, 4];
eq2 = SetPrecision[eq2, 4];
Do[a2 = NSolve[{eq1, eq2}, {x, y}, Reals], {100}] // Timing

{Sort@a1,Sort@a2}

(*

{1.326008, Null}
{0.826805, Null}

{{{x -> 0.0712826, y -> -0.641068}, {x -> 0.146691, y -> 0.796314},
  {x -> 38.5495, y -> 2.1632}, {x -> 39.1885, y -> -2.02844}},
 {{x -> 0.07, y -> -0.6411}, {x -> 0.15, y -> 0.7963}, 
  {x -> 38.55, y -> 2.163}, {x -> 39.19, y -> -2.028}}}

*)

Speed difference depends on equations, but I've used this to speed things where high precision is not needed...

Answer 3

Because WorkingPrecision determines the minimum number of digits used in the calculations, you can reduce it, if you hope to reduce time by reducing accuracy. However, WorkingPrecision less than MachinePrecision, the default value, is unlikely to have a large effect on timing, as you can see from,

Table[First@Timing[Do[NSolve[x^5 - 3 x^4 + 3 x^3 - 4 x^2 + 15 x == 7, 
     WorkingPrecision -> wp], {i, 1000}]], {wp, 3, 15, 3}]
(* {0.984375, 0.984375, 0.968750, 0.984375, 1.031250} *)