ZERO_RC
Nonlinear Equation Solver, Reverse Communication

ZERO_RC is a C++ library which seeks solutions of a scalar nonlinear equation f(x)=0, or a system of nonlinear equations, using reverse communication (RC).

One of the standard problems in numerical analysis is to determine an approximate solution to a scalar nonlinear equation of the form f(x)=0.

Reliable and efficient procedures for this task, sometimes called "zero finders" or "root solvers" are available in many libraries. These procedures typically require the user to write a sub-procedure to evaluate the function for any argument x; the form and list of arguments for this sub-procedure are strictly prescribed by the library procedure. The user must somehow make this sub-procedure available to the solver, either by using a fixed name for the sub-procedure, or by passing in the actual name as an argument.

In many cases, it can be inconvenient to use such a library routine, because it is inserted between the main user program and the user function. This means that data defining the function, which might be chosen in the main program, must then somehow be communicated to the user function, perhaps by declaring some kind of global memory, or by sneaking the data through in an extra argument provided by the library procedure, or by the use of auxilliary data files.

Moreover, the user essentially loses control of the process until the library procedure returns. It might, however, be the case that the user could detect important error conditions, or gather useful information, if the intermediate x values generated by the library procedure were visible.

If we denote this typical method of interaction between a user and a library an instance of "forward communication", then there is an alternative approach, known as "reverse communication", which allows the user much more freedom in designing the function evaluation, and in observing and intervening in the iteration that is seeking the solution.

An idealized version of the use of a reverse communication zero finder might look like this:

        x = initial approximation.
        while ( not satisfied )
          fx = f(x)
          x = root ( x, fx )
        end
      

• The function f(x) is evaluated within the main program. The user could write an actual procedure to evaluate f(x), but in that case the user is free to design the interface to f(x) in any desired way. More importantly, the user can evaluate f(x) directly in the main program, and has access to all the data in the main program that might be needed to evaluate the function;
• The user sees every iterate x produced by the zero finder. This means the user can catch and occasionally correct problems that might arise if x goes out of prescribed bounds; the user can print a table of the computed values, or plot the sequence of function values.

Reverse communication zero finders can be very useful in situations where the function to be evaluated is actually the outcome of a complicated process. For instance, if we are seeking an eigenvalue x that makes the determinant of some matrix zero, then our function evaluation may require us to form a large matrix and to factor it in order to evaluate the determinant. This may be cumbersome to do if we must perform all these operations in a sub-procedure.

Similarly, we might be solving a boundary value problem using the shooting method, and f(x) might be the deviation at the final time between the computed and desired boundary values. In that case, a subprocedure formulation would require us to set up and solve a boundary value problem repeatedly in an isolated piece of code.

Licensing:

The computer code and data files described and made available on this web page are distributed under the GNU LGPL license.

Languages:

ZERO_RC is available in a C version and a C++ version and a FORTRAN77 version and a FORTRAN90 version and a MATLAB version.

Related Data and Programs:

BACKTRACK_BINARY_RC, a C++ library which carries out a backtrack search for a set of binary decisions, using reverse communication (RC).

BISECTION_RC, a C++ library which seeks a solution to the equation F(X)=0 using bisection within a user-supplied change of sign interval [A,B]. The procedure is written using reverse communication (RC).

BRENT, a C++ library which contains routines for finding zeroes or minima of a scalar function of a scalar variable, without the use of derivative information, including a reverse communication option, by Richard Brent.

CG_RC, a C++ library which implements the conjugate gradient method for solving a positive definite sparse linear system A*x=b, using reverse communication (RC).

SORT_RC, a C++ library which can sort a list of any kind of objects, using reverse communication (RC).

TEST_ZERO, a C++ library which implements test problems for the solution of a single nonlinear equation in one variable.

Reference:

1. Gaston Gonnet,
   On the Structure of Zero Finders,
   BIT Numerical Mathematics,
   Volume 17, Number 2, June 1977, pages 170-183.
2. Werner Rheinboldt,
   Algorithms for finding zeros of a function,
   UMAP Journal,
   Volume 2, Number 1, 1981, pages 43-72.

Source Code:

• zero_rc.cpp, the source code.
• zero_rc.hpp, the include file.
• zero_rc.sh, BASH commands to compile the source code.

Examples and Tests:

• zero_rc_prb.cpp, a sample calling program.
• zero_rc_prb.sh, BASH commands to compile and run the sample program.
• zero_rc_prb_output.txt, the output file.

List of Routines:

• ROOT_RC solves a single nonlinear equation using reverse communication.
• ROOTS_RC solves a system of nonlinear equations using reverse communication.
• R8MAT_FS factors and solves a system with one right hand side.
• R8_EPSILON returns the R8 roundoff unit.
• R8_HUGE returns a "huge" R8.
• R8_SIGN returns the sign of an R8.
• TIMESTAMP prints out the current YMDHMS date as a timestamp.

You can go up one level to the C++ source codes.