Re: Branch & bound for not everywhere defiend constraints
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