multi_newton_run¶

A Multi-Threaded Newton’s Method¶

Syntax¶

ok = multi_newton_run ( xout ,
      fun , num_sub , xlow , xup , epsilon , max_itr , num_threads
)

Purpose¶

Multi-threaded determination of the argument values \(x\), in the interval \([a, b]\) (where \(a < b\)), such that \(f(x) = 0\).

Thread¶

It is assumed that this function is called by thread zero, and all the other threads are blocked (waiting).

Method¶

For \(i = 0 , \ldots , n\), we define the i-th grid point \(g_i\) by

\[g_i = a \frac{n - i}{n} + b \frac{i}{n}\]

For \(i = 0 , \ldots , n-1\), we define the i-th sub-interval of \([a, b]\) by

\[I_i = [ g_i , g_{i+1} ]\]

Newton’s method is applied starting at the center of each of the sub-intervals \(I_i\) for \(i = 0 , \ldots , n-1\) and at most one zero is found for each sub-interval.

ok¶

The return value ok has prototype

bool ok

If an error occurs, it is false, otherwise it is true.

xout¶

The argument xout has the prototype

vector<double>& xout

The input size and value of the elements of xout do not matter. Upon return from multi_newton , the size of xout is less than or equal the number of sub-intervals \(n\) and

\[| f( xout[i] ) | \leq epsilon\]

for each valid index 0 <= i < xout . size () . Two \(x\) solutions are considered equal (and joined as one) if the absolute difference between the solutions is less than \((b - a) / n\).

fun¶

The argument fun has prototype

void fun ( double x , double& f , double& df )

This function must evaluate \(f(x)\), and its derivative \(f^{(1)} (x)\), using the syntax

fun ( x , f , df )

where the arguments to fun have the prototypes

      double x
      double& f
      double& df

. The input values of f and df do not matter. Upon return they are \(f(x)\) and \(f^{(1)} (x)\) respectively.

num_sub¶

The argument num_sub has prototype

size_t num_sub

It specifies the number of sub-intervals; i.e., \(n\).

xlow¶

The argument xlow has prototype

double xlow

It specifies the lower limit for the entire search interval; i.e., \(a\).

xup¶

The argument xup has prototype

double xup

It specifies the upper limit for the entire search interval; i.e., \(b\).

epsilon¶

The argument epsilon has prototype

double epsilon

It specifies the convergence criteria for Newton’s method in terms of how small the function value must be.

max_itr¶

The argument max_itr has prototype

size_t max_itr

It specifies the maximum number of iterations of Newton’s method to try before giving up on convergence (on each sub-interval).

num_threads¶

This argument has prototype

size_t num_threads

It specifies the number of threads that are available for this test. If it is zero, the test is run without the multi-threading environment.

Source¶

namespace {
bool multi_newton_run(
   vector<double>& xout                       ,
   void fun(double x, double& f, double& df)  ,
   size_t num_sub                             ,
   double xlow                                ,
   double xup                                 ,
   double epsilon                             ,
   size_t max_itr                             ,
   size_t num_threads                         )
{
   bool ok = true;
   ok     &= thread_alloc::thread_num() == 0;

   // setup the work for num_threads threads
   ok &= multi_newton_setup(
      num_sub, xlow, xup, epsilon, max_itr, num_threads
   );

   // now do the work for each thread
   if( num_threads > 0 )
      team_work( multi_newton_worker );
   else
      multi_newton_worker();

   // now combine the results for all the threads
   ok &= multi_newton_takedown(xout);

   return ok;
}
}