| Thread Links | Date Links | ||||
|---|---|---|---|---|---|
| Thread Prev | Thread Next | Thread Index | Date Prev | Date Next | Date Index |
Dear colleagues, Here is an example that shows IMO that NaI are not the best option for dealing with the evaluation of function over intervals that may not be included in their domain. Consider f(x)=sqrt(x-1). We wish to verify whether there is a fixed point or not inside a given interval xx. First, let us consider xx=[0.75,1.25]. Then f(xx)=sqrt([-0.25,0.25])=[0,0.5]. Because the intersection between xx and f(xx) is empty, we have proved that there is no fixed point inside xx. Second, let us consider xx=[0,2]. Then f(xx)=sqrt([-1,1])=[0,1]. Although f(xx) is a subset of xx, we cannot conclude that there is a fixed point inside xx because sqrt was evaluated on an interval that is not included in its domain. And indeed, f has no fixed point in xx as shown by the attached graphic. The second case does show that we need to output the information that a function has potentially been evaluated on an interval that is not contained in its domain. However, if NaI are used to this purpose, then both the first and the second case will return NaI. Thus, we loose the interpretation of the first computation that allowed to prove the absence of fixed point in the interval. It would be quite harmful to require the user to duplicate his computations using different modes, or to switch between different modes depending on the purpose of his computation. Kind regards, Alexandre Goldsztejn On Wed, Sep 2, 2009 at 5:16 PM, Nate Hayes<nh@xxxxxxxxxxxxxxxxx> wrote: > Arnold Neumaier wrote: >> Vincent Lefevre schrieb: >>> On 2009-09-01 14:00:14 -0400, Nate Hayes wrote: >>>> Arnold Neumaier wrote: >>>>> Correct is the following code, which uses Section 3.4 of the >>>>> Vienna proposal that must be considered whenever existence >>>>> statements are made (also in existence from an interval Newton >>>>> operator): >>>>> >>>>> if isEmpty(f(X')) delete X' >>>>> else if inf(f(X')) > 0 delete X' >>>>> else if PossiblyUndefined bisect or save X' >>>>> else if f(X') <= 0 accept X' >>>>> else bisect or save X' >>>> Yes, but this requires global/local flags, which I think are to be >>>> avoided in data-parallel computing environments. In the context of >>>> this type of algorithm, the interval result is of no use when >>>> PossiblyUndefined is set, anyways. So it is better to return a >>>> "PossiblyUndefined" (or in some cases perhaps a "TotallyUndefined") >>>> NaI instead. >>> >>> One could also have a flag attached to the returned interval. >>> Alternatively, one could have a function telling whether X' is >>> included in the domain of f. >> >> The latter can in general be found out only by evaluating; >> so this would double the work whenever one needs both the >> evaluation and the domain check. >> >> Producing NaI in such a situation also wastes information available, >> since one can no longer check for the first two cases >> in the above piece of code. > > For certain interval algorithms, these checks are not necessary; so it is > not a waste of information, since the interval result is of no use when the > operation is invalid. I suspect for other algorithms the flags may be of no > use, too. The most optimal choice appears to depend on what is the interval > algorithm the user is trying to accomplish. > > It may be useful for us to try and classify these different cases and > algorithms. > > > >> If flags are to be avoided, flag-raising operations should return >> two results: the range enclosure and a byte encoding all relevant >> flags. In this way, the compiler can decide whether it wants to >> exploit the flag byte, ignoring or using it as required by an algorithm. >> One one only needs to have the compiler provide different constructs, >> e.g., >> y=sqrt(x) for the ``ignore flags'' mode, >> (y,flagbyte)=sqrt(x) for the ``use flag'' mode, >> both interpreted at the implementation level via the second construct. >> This is very easy to use, and easily parallelizes. >> >> >> The PossiblyUndefined would then be a result of the function >> evaluation algorithm rather than one of the underlying interval >> arithmetic. This even has the advantage that a user can skip further >> operations >> in cases that a flag makes superfluous the remaining part of a >> computation. > > Mostly it seems problematic it would apparently require non-power of two > registers and busses in a hypothetical Vector Processing Unit, for example. > Or nonstandard bit encodings of the floating-point numbers to make room for > the extra flag bits. > > Otherwise, sending an extra byte along with the interval datatype is very > wasteful if both will never be used by the user at the same time. This is > why packing the byte into a NaI (and hence several NaIs) in some cases I > think is a very attractive option. This way, only if the user truly needs > both the interval result and the flag information will he need to suffer the > potential consequences of sending the extra byte along. > > >> >> The same technique also works in all other cases where the Vienna >> proposal recommended the use of flags. > > I agree in principle. I think this also shows that NaI is not too > theoretical, and is in fact quite a well-understood concept. The difficult > and remaining questions seem to simply be implementation details, e.g., > should NaI be implemented as a mode, a flag or both, etc. > > Nate Hayes > -- Dr. Alexandre Goldsztejn CNRS - University of Nantes Office : +33 2 51 12 58 37 Mobile : +33 6 78 04 94 87 Web: www.goldsztejn.com Email: alexandre.goldsztejn@xxxxxxxxxxxxxx
Attachment:
motivation.jpg
Description: JPEG image
