Prev Next multi_newton_run

@(@\newcommand{\W}[1]{ \; #1 \; } \newcommand{\R}[1]{ {\rm #1} } \newcommand{\B}[1]{ {\bf #1} } \newcommand{\D}[2]{ \frac{\partial #1}{\partial #2} } \newcommand{\DD}[3]{ \frac{\partial^2 #1}{\partial #2 \partial #3} } \newcommand{\Dpow}[2]{ \frac{\partial^{#1}}{\partial {#2}^{#1}} } \newcommand{\dpow}[2]{ \frac{ {\rm d}^{#1}}{{\rm d}\, {#2}^{#1}} }@)@
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;
}
}
Input File: example/multi_thread/multi_newton.cpp