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}} }@)@This is cppad-20221105 documentation. Here is a link to its current documentation .
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