A Multi-Threaded Newton's Method

Loading [MathJax]/extensions/TeX/newcommand.js

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