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

Re: Branch & bound for not everywhere defiend constraints

Vincent Lefevre schrieb:

On 2009-09-02 11:26:21 +0200, Arnold Neumaier wrote:

Vincent Lefevre schrieb:

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.


I would have said the opposite, i.e. that the latter doesn't need
evaluation in general. For instance, if the domain is R, then the
result is always TRUE. For the division, the result is TRUE iff
the second argument doesn't contain 0.
I meant the domain of a whole expression. For example to get POssiblyUndefined for a function r(x) given as a 
continued fraction, for x in xx, one needs to evaluate r(xx)
-- a factor 2 of overhead, The same holds when r(x) is the
square root of an arbitrary expression.

When a rational function is given as r(x)=p(x)/q(x), one needs
to evaluate at least q(xx) -- a factor 1.5 of overhead if p and q
have the same degree.

Even when r(x) is only a multivariate polynomial, one needs to
find this out - though this may be done at compile time.

So how much overhead there is clearly depends on the actual expression.



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.


This is what I've said: a flag *attached to the returned interval*.


I had intended to say something slightly different:
_all_ flags attached to the returned interval.


Arnold Neumaier