Re: Branch & bound for not everywhere defined constraints
John Pryce wrote:
> B1. Sometimes, if "possiblyUndefined" is reported one
> isn't much interested to know the value of ff(X).
> B2. Sometimes one just wants to know ff(X) and is unconcerned
> whether "possiblyUndefined" was reported or not.
> B3. But sometimes one wants ff(X) AND one wants to know
> whether "possiblyUndefined" was reported.
>
> ...
>
> Suppose ff is vectorised, i.e. each elementary operation acts
> component-wise on vectors of fixed length n to produce an output of
> length n.
> - In the calling program, define a flag array FLAG of length n,
> initialised to 0.
> - Call a system-function that stores the address of FLAG in a
> register pFLAG known to all the library functions.
> - Call ff. Each vector operation, say ww = uu op vv, is coded so that
> it records the status component-wise in FLAG. That is, if
> uu[i] op vv[i] raises "possiblyUndefined",
> then by indirection through pFLAG, it sets FLAG[i] to 1.
>
> On return from ff, the array FLAG (which is local to the calling
> program) equals 1 in exactly those components for which the
> calculation raised "possiblyUndefined".
>
> Nate, is such a scheme efficiently implementable? If so, it seems to
> handle cases B1, B2 and B3 above without the tags on intervals, or
> extra (explicit) output arguments of operations, required by
> solutions D1, D2 above.
Dear John,
Obviously, for case B2 we don't need to conern ourselves with the flags. So
the interesting cases are B1 and B3. IMHO, what you describe (or something
along these lines) is most likely required for B3. However, for B1, why must
the user bother allocating the extra memory for the flags? It seems much
better to just allow the hardware to update the ww array, placing
"possiblyUndefined" NaI results in those ww elements which require them and
valid [double,double] interval results in those ww elements that don't. This
would be more effecient than case B3, since it doesn't require allocating
memory, and also it reduces the bandwith to the processor by about 1/2. So
maybe the hypothetical interval hardware supports both B1 and B3 types of
vector operations.
Sincerley,
Nate