Thread Links Date Links
Thread Prev Thread Next Thread Index Date Prev Date Next Date Index

Re: Branch & bound for not everywhere defiend constraints

Arnold Neumaier schrieb:

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.


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.
The same technique also works in all other cases where the Vienna proposal recommended the use of flags. 


Arnold Neumaier


We used two different types in a C++ test-implementation.
An Interval and a type called ExpressionResult. The ExpressionResult keeps an interval together with some flags.
For further details see the attached paper for the proceedings of SCAN08 (joint work with J. Wolff v. Gudenberg) 


--
     o           Marco Nehmeier, Lehrstuhl fuer Informatik II
    / \          Universitaet Wuerzburg, Am Hubland, D-97074 Wuerzburg
InfoII o         Tel.: +49 931 / 31 88684
  / \  Uni       E-Mail: nehmeier@xxxxxxxxxxxxxxxxxxxxxxxxxxx
 o   o Wuerzburg

Attachment: article.pdf
Description: Adobe PDF document