Raised by Markus Neher and others at Schloss Dagstuhl meeting, 21-26 Nov 1999:
The following example of Sun's closed interval arithmetic leads to the wrong answer from SQRT (negative) is [empty]. Since we get an enclosing interval, we conclude that SQRT (x-1) must have a fixed point in [-1, 5], which it does not.
! File: Neher/no_fixed_point.f90 25 Nov 1999 ! ! Purpose: Illustrate WRONG conclusion from sqrt(negative) ! Author: Markus Neher, Universitaet Karlsruhe ! Coder: George Corliss, Marquette University ! Results: ! Has fixed point ! X0 = [-1.0,5.0] ! X = [0.0E+0,2.0] ! ! Clearly, X is in the interior of X0 ! The fixed point theory would appear to imply ! that SQRT (x-1) has a fixed point in [0, 2] ! ! Falicy: The fixed point theory requires f(x) ! to be continuous on X, which SQRT (x - 1) is not. program No_Fixed_Point INTERVAL, PARAMETER :: X0 = [-1, 5] INTERVAL :: X X = X0 X = SQRT (X - 1) ! Sorry, but I don't remember the operator for INTERIOR if (inf(X0) < inf(X) .and. sup(X) < sup(X0)) then print *, "Has fixed point" end if print *, "X0 = ", X0 print *, "X = ", X end program No_Fixed_Point
Error: User must check for continuity.
That may be a hard pill to train users to swallow.
The problem does not depend on arguments being partially outside the domain of a function with a finite domain. Consider, for example:
ANINT([.75, 1.25]) = 1.0The fundamental problem is that it is the user/programmer's responsibility to make sure the assumptions for the application of the interval Newton or Bower fixed-point theorem are met, as George points out, and as I presented in my paper at the SIAM annual meeting in Atlanta.
We are considering how to implement a way for users to test that all sub-expressions within a function are strictly within the domain of each operation and/or intrinsic. Of course, for this to work with user functions, an additional interface will be required.
Thanks to Markus Neher for raising this question. I will be sure to add an additional section to the user docs on this point.
Markus's SQRT (x - 1) example generated MUCH discussion at the Dagstuhl meeting last week. It turns out that it was formulated jointly by several people on a walk through the fields and forest near the castle. Exactly the type of interaction the organizers wish for. It also served to make sure everyone knew that your compiler is available, although we could have had more favorable press :-)
It seems Sun's design goals were somewhat different from those of the designers of the XSC languages. Both agree that containment is fundamental. Your closed arithmetic is elegant, logical, and very practical. However, please try for a moment to see what it looks like to XSC users. The XSC languages are quite happy to generate exceptions causing fatal program crashes. I do not know whether it was an explicit design goal, but as far as anyone I talked to at Dagstuhl can think, if an XSC program for a function contains no IF (or a ? b : c in C-XSC) then [does not crash] implies continuous! If f([x]) runs, f is continuous in [x].
This is VERY useful in practice, since fixed point theorems have continuity hypotheses, so it is VERY useful to have this as an automatic hypothesis validation technique. Further, the few cases of continuous, but potentially non-differentiability are easily check at very low cost by the AD operators, so you almost have [runs] implies analytic.
In this setting, arguments outside the domain of a function are NOT program errors, any more than an empty intersection in an interval Newton is an error. It is a valid, useful conclusion.
Yes, your closed arithmetic DOES compute correct enclosures in many cases for which the XSC languages crash. That is good. At the same time, this looks to their users as a loss of an essential feature of the languages.
> The problem does not depend on arguments being partially outside the > domain of a function with a finite domain. Consider, for example: > ANINT([.75, 1.25]) = 1.0XSC languages do not implement such operators for interval functions. I understand why you do, but it is partly by assuming that you must be backward compatible with real arithmetic that you build a problem for yourself.
> The fundamental problem is that it is the user/programmer's > responsibility to make sure the assumptions for the application > of the interval Newton or Bower fixed-point theorem are met, > as George points out, and as I presented in my paper at the > SIAM annual meeting in Atlanta.Yes, but but how? Checking continuity is HARDER to automate than the containment hypothesis. We need all the help we can get. Without [runs] ==> continuous, it is VERY difficult for the user to check continuity, which is just as important a hypothesis as containment.
> We are considering how to implement a way for users to test that > all sub-expressions within a function are strictly within the > domain of each operation and/or intrinsic. Of course, for this > to work with user functions, an additional interface will be > required.PLEASE! One possibility might be a compiler command line switch. If I say
f95 -xia -xtest-continuity myProgram.f90then any argument outside the domain of definition (or at a point of possible discontinuity) is a fatal error. Under that flag, you use a set of operations that check their domains at run time, and I am saying that I am willing to bear the cost in speed and possible failing to get enclosures I could get otherwise. Also, overflows should be fatal, or they become a hole for possible containment failures. In neither case should enclosures fail.
Better would be testing I can switch on or off at run time, but that is probably too expensive.
Another possibility is simply a module that hides the standard functions with domain problems, checks their domains, and calls the hidden function. There would be a performance penalty, but probably minor, unless LOTS of operators from that module are used, in which case, I guess I really want that security. If the module is provided in source, I could choose which operators to check and which to use as is, a possibly useful, and possibly dangerous, solution.
I see this from the user's perspective as a trade-off of a tool for continuity validation vs a larger set of expressions for which I can compute validated bounds. I am inclined to agree with the XSC folks that some reduction in the set of applicability is a small price to pay for a continuity validation tool. How else can I check continuity on the computer?
This is really about fine-grained user definition and control of exceptions, isn't it? Does it help to back the discussion up to the level of defining and handling exceptions?
The XSC users at Dagstuhl felt very strongly about this issue. They say they will not use your f95 if it means they must check their own continuity without tools for doing so.
George F. Corliss
If you have a question related to validated computing, interval analysis, or related matters, I recommend