Interval valuation and the Problem_Expression package

This package allows to deal automatically with expressions that cannot be evaluated using interval arithmetic for some range for the unknowns. Their purpose is to create ALIAS_F and ALIAS_J procedures that will be used by MakeF and MakeJ.

The first procedure in this package is Problem_Expression that will create a list A_CONSTS of constraints that must be verified to be able to evaluate an expression. The end-user may provide information on constraints that will always be satisfied by writing them in the global list variable A_CONSTS_ALWAYS_OK.

The syntax of Problem_Expression is:

 
Problem_Expression(expr)

For example

 
Problem_Expression(x/(y-2)+sqrt(x+1));

will produce the list

 
[y - 2 <> 0, -x - 1 <= 0]

that indicates that the denominator of x/(y-2) must not include 0 and that the argument of sqrt cannot be an interval that includes negative numbers. Note that some element of this list of constraints may be used to speed up the solving of a problem by using the HullIConsistency procedure (see section 4.2.1) that will modify the ranges of the unknowns so that the expressions may be evaluated or even reject ranges for which one (or more) expression cannot be evaluated.

This procedure deals with the following evaluation problems:

• denominator that may include 0
• argument of square should be positive
• argument of arcsin and arccos should be included in [-1,1]
• argument of log,ln,log10 should be positive
• argument of arccosh should be greater than 1
• argument of arctanh cannot have an intersection with the interval [-1,1]
• argument $x$ of $x^y$ where $y$ is not an integer should be positive
• argument $x$ of $exp(x)$ should not be too large to avoid overflow problem.

Using the constraints produced by Problem_Expression the Verify_Problem_Expression procedure will create an ALIAS_F procedure to be used by MakeF. It uses the following rules for the evaluation of an expression expr:

• if the constraint is $x\le 0$ where $x=[\underline{x},\overline{x}]$
  • if $\underline{x}$ is positive expr will be set to [`ALIAS/low_value_expr_violated`,`ALIAS/high_value_expr_violated`]
  • if $\underline{x}\ge$ -`ALIAS/close_to_zero` and $\overline{x}>0, \le$ `ALIAS/close_to_zero` expr will be set to [
    `ALIAS/low_value_expr_violated`, `ALIAS/high_value_expr_violated`]
  • if $\underline{x}<0$ and $\overline{x}$ is positive expr will be set to the interval [`ALIAS/lower_bound_uneval_expr`, `ALIAS/upper_bound_uneval_expr`]
• if the constraint is $x \not= 0$
  • if $\vert\underline{x}\vert, \vert\overline{x}\vert \le$ `ALIAS/close_to_zero` expr will be set to [
    `ALIAS/low_value_expr_violated`, `ALIAS/high_value_expr_violated`]
  • if $x$ includes 0 or ( $\underline{x}<0$ and $\vert\underline{x}\vert<$ `ALIAS/close_to_zero`) or ( $\overline{x}>0$ and $\vert\overline{x}\vert<$ `ALIAS/close_to_zero`) expr will be set to the interval [`ALIAS/lower_bound_uneval_expr`, `ALIAS/upper_bound_uneval_expr`]
• if the constraint is $x \cap [-1,1]=\emptyset$ (for the arccoth function) and $x$ has an intersection with this interval then expr will be set to the interval [`ALIAS/lower_bound_uneval_expr`, `ALIAS/upper_bound_uneval_expr`]
• if we deal with $e^x$
  • if $\underline{x}<$200 and $\overline{x}>200$ then expr is set to the interval [ $e^{\underline{x}},e^{\underline{x}}+10^{50}$]
  • if $\underline{x}>$200 then xpr is set to [ $10^{50},10^{60}$]
• if the constraint is $x \subset [-1,1]$ (for the arcsin, arccos functions) then
  • if $\underline{x}<-1$ or $\overline{x}>1$ then expr will be set to [
    `ALIAS/low_value_expr_violated`, `ALIAS/high_value_expr_violated`]
  • if $\underline{x}<-1$ and $\overline{x}\le 1$ then $x$ will be set to $[-1,\overline{x}]$
  • if $\overline{x}>1$ and $\underline{x}\ge -1$ then $x$ will be set to $[\underline{x},1]$

The syntax of the procedure is

 
Verify_Problem_Expression(EQ,VAR)

where EQ is a list of expressions and VAR a list of unknown names. The global list variable `ALIAS/Problems will contain the number of evaluation problems detected for each element of EQ.

This procedure generates also a C++ file ALIAS_F_AUTOMATIC.c with two procedures

• Is_Evaluable(INTERVAL_VECTOR X) that returns 1 if all the expressions in EQ can be evaluated when the unknown VAR have as range X
• Is_Evaluable(INTERVAL_VECTOR X), int i that returns 1 if all the i-th expression in EQ can be evaluated when the unknown VAR have as range X

Note that of the string `ALIAS/ID` is not empty the created procedure will be ALIAS_F_AUTOMATIC`ALIAS/ID`.c and will contain the procedures named Is_Evaluable`ALIAS/ID`. For example if `ALIAS/ID` has been set to "100" the file will be ALIAS_F_AUTOMATIC100.c which will include the routines Is_Evaluable100.

If these procedures have been created, then the flag `ALIAS/has_test_evaluate` will be set to 1 (the procedure uses also the internal flag `ALIAS/test_evaluate`) to determine what should be done when a non-evaluability condition is satisfied for a given variable U. The code will be

 
if (non evaluable condition) {
          U=default value;
          goto next[i];} #if `ALIAS/test_evaluate`=0, i being computed
          return 0;}     #if `ALIAS/test_evaluate`=1
          }              #`ALIAS/test_evaluate`=2
         goto next[i];}   #`ALIAS/test_evaluate`=3, i =ALIAS_Next
U=real U value;
next[i]: ;
if (non evaluable condition) {
           ....

If `ALIAS/test_evaluate` is set to 3 the label number is given by the global ALIAS variable ALIAS_Next.

These procedures may be used to test if an expression may be evaluated before using them for a filtering algorithm. For example the HullConsistency, HullIConsistency and Simp2B that implement the 2B filtering use automatically these procedures as soon as Verify_Problem_Expression has been called before their use (but Verify_Problem_Expression has to be called with the same list of unknowns and variables than the consistency procedures).

Note that Verify_Problem_Expression may have a third argument which is a string (e.g. "ALIAS_Coeff"). In that case instead of creating the ALIAS_F_AUTOMATIC file with the ALIAS_F Maple procedure the file ALIAS_Coeff will be created describing the Maple procedure ALIAS_Coeff(fid,i). If this procedure is called for expression i of func the procedure will create in the file described by fid the C++ code necessary to determine if this expression can be interval-valuated. If not then it is necessary to affect the i-th element of the interval vector that will be returned by the procedure. As we do not know the name of this vector it shall be indicated as the fourth argument of Verify_Problem_Expression. Hence

 
Verify_Problem_Expression(func ,Vars,"ALIAS_F_AUTOMATIC","V")

is equivalent to Verify_Problem_Expression(func ,Vars). See an application of this use in section 8.3.

The Verify_Problem_ExpressionJ procedure creates in the same way a Maple procedure ALIAS_J. The rules are identical but the syntax of the procedure is

 
Verify_Problem_ExpressionJ(J,VAR)

where J is an array that define the jacobian of EQ with respect to VAR. A typical call to this procedure is

 
with(linalg):
J:=jacobian(EQ,VAR):
Verify_Problem_ExpressionJ(eval(J),VAR)

The name of the variables that allows one to specify what should be the return value of the expression are: `ALIAS/low_value_exprJ_violated`, `ALIAS/high_value_exprJ_violated`.

Note that in the C++ procedures generated by MakeF, MakeJ if an evaluation problem occurs the C++ flags ALIAS_ChangeF, ALIAS_ChangeJ will be set to 1 (default value 0) to indicate that the resulting computed value should be used with some care.