[std-interval] csets

[Dr John Pryce]

Ray and all

At 21:00 05/06/06, Ray Moore wrote:
>The one thing that bothers me about the cset approach is
>returning a result like [0, 1] when feeding the argument
>[-4, 1] to the square root function. I mean there is a very useful 
>extension of the square root function to complex values, for which 
>the result would be something else, like
>[0, 1] U [-2, 2] i.
>
>I understand the difficulty of allowing complex values. To make it 
>complete would be another huge project on top of all that is already underway.
>
>However, otherwise it will necessary to explain the restriction to 
>real results. Furthermore, things like
>(sqrt [-4, 1])^4 would produce [0, 1] without including complex 
>numbers, whereas it should produce [0, 16]
>with complex numbers allowed.
>
>What is the proposal for dealing with such concerns ?

I will answer the query "how to apply csets over the complex 
numbers?" (mathematics). That leaves aside the important question of 
"when, in a program, to decide to move from the reals to the complex 
numbers?" (language and library design and semantics).-

To set up a cset system you need
- An underlying number system S - preferably a field such as the 
reals or complex numbers of course.
- A compact topological space S* in which S is embedded as a dense subset.

Then the cset value of any (possibly vector) "function of 
S-variables", i.e. f : S^n -> S^m, is defined for any subset of 
(S*)^n to be a subset of (S*)^m, defined in terms of graph closure. 
Compactness implies the Fundamental Theorem holds, which ensures 
containment in the resulting interval system.

To convert this into an interval cset system you need
- A set I of subsets of S* that you deem to be "intervals". They must 
be compact, and the S* must be a member of I.
- An algorithm "interval hull" that encloses an arbitrary subset X of 
S* in a member of I, call it hull(X). This is the "exact arithmetic" version.

To convert this to a machine interval cset system you need
- A subset I_T of I, deemed to be the "machine intervals" for a given 
machine version T of the underlying system S.
- An algorithm "machine interval hull" that encloses an arbitrary 
subset of S* in a member of I_T, call it hull_T(X).

   I guess hull_T(X) must always enclose hull(X). Not a problem when 
intervals are boxes in (R*)^m, but a bit tricky when intervals are 
wrap-around ones (not always an obvious UNIQUE exact hull), or discs 
in the complex plane (easily get a good-enough, but not easily a 
best, machine hull).

That summarizes the theoretical needs. Rump's INTLAB has an 
implementation with intervals being *finite* discs in the complex 
plane C. The most natural compact extension C* is C plus one point at 
infinity, as used for 150 years in complex analysis. The set I could 
then be all the finite discs, plus the "infinite discs" which are 
half-planes, plus the whole of C*, plus the empty set. This set is 
closed under +, - and reciprocal (not multiplication or division).

The set I_T could be all discs that have machine-representable centre 
and radius - with a special way to represent the half planes.

I haven't worked on this system, so I don't know any of the practical 
snags. But it makes sense in principle.

John

Dr John and Mrs Kate Pryce
142 Kingshill Rd
Swindon, Wiltshire SN1 4LW
UK
Tel (+44)1793-331062