Re: motion 35
Ulrich, P1788,
A technicality: one doesn't actually divide by an interval containing zero
in the extended interval Newton; rather, the zero is silently removed from
the denominator, bisecting the denominator into two semi-open intervals. For
example, the zero is removed from the denominator of the reciprocal
1/[-1,1]
in a Newton step, effectively bisecting the denominator into two semi-open
intervals
[-1,0) and (0,1]
which are then pushed onto a stack or queue to be processed separately by
the algorithm. So the fundamental operation here is not division by an
interval containing zero, but rather division by an interval with an open
endpoint at zero.
We all know that the classic interval arithmetic of Moore and Sunaga is
restricted to closed and bounded intervals, and this is why division by a
semi-open interval is an undefined operation. But P1788 already accepted
this since Motion 8. For example, the decorated interval operation
1/[0,1] = ([1,+Inf],somewhereUndefined)
has the dual meaning:
-- 1/[0,1] = 1/(0,1] = [1,+Inf] // Motion 5 arithmetic
-- 1/[0,1] = somewhereUndefined // Moore/Sunaga arithmetic
Kaucher arithmetic in this sense is no different than Moore/Sunaga
arithmetic, i. e., real intervals, set-based intervals, standard intervals,
classical intervals and Kaucher intervals are all united because of the
decoration framework.
Modal intervals fit into this framework, too. For example, the extended
interval Newton can be run on a modal interval processor since both of the
semantic theorems
(all x in (0,1])(exists y in [1,+Inf]) : y = 1/x // *-theorem
(all y in [1,+Inf])(exists x in (0,1]) : y = 1/x // **-theorem
are true and this is proof the solution [1,+Inf] is unique.
So I see nested sets of interval arithmetic:
-- Moore/Sunaga arithmetic is a subset of Motion 5 arithmetic
-- Motion 5 arithmetic is a subset of modal interval arithmetic
-- Moore/Sunaga arithmetic is a subset of Kaucher arithmetic
-- Kaucher arithmetic is a subset of modal interval arithmetic
Modal interval arithmetic is the superset of everything, Moore/Sunaga
arithmetic is the subset of everything and decorations tie it all together.
The question most interesting to me is if P1788 chooses to standardize only
one of the subsets, if it will do this in such a way that makes the
supersets (or even the other subsets) incompatible and hence requiring
different standards. Since we don't know the outcome yet, we are hedging our
bets and have already begun to develop a separate standard for modal
interval arithmetic that we will follow, as well as a programming guide for
a modal interval ASIC all the way down to Level 4. Our goal is to make it as
close to P1788 as possible. These documents will eventually be published and
maintained on our website for anyone that is interested. In the meantime,
anyone who wishes to review or contribute to the project can contact me
offline.
Nate
P.S. I talk about reciprocal of semi-open interval. I know there are not
actually semi-open intervals in P1788. But if X is a closed interval and f
is a real function with natural domain Df, P1788 restricts f to the
intersection of X and f. So for the reciprocal function f(x)=1/x on the
closed interval X=[0,1],
Df \intersect X = (0,1].
----- Original Message -----
From: "Ulrich Kulisch" <ulrich.kulisch@xxxxxxx>
To: "stds-1788" <stds-1788@xxxxxxxxxxxxxxxxx>
Sent: Thursday, June 28, 2012 11:02 AM
Subject: motion 35
Dear P1788 members.
We are supposed to develop a standard for interval arithmetic. All kinds
of intervals have already been invented or developed. Real intervals,
set-based intervals, standard intervals, classical intervals, common
intervals, conventional intervals, wrap around intervals, Kaucher and
modal intervals, and so on. Frequently only the context tells you what
kind of interval is meant.
For me a 'real interval' is a closed and connected set of real numbers,
an element of the set \overline{IR}. Let me argue a little about this.
Zero finding is a central task of mathematics. In conventional numerical
analysis Newton's method is the key method for computing zeros of
nonlinear functions. It is well known that under certain natural
assumptions on the function the method converges quadratically to the
solution if the initial value of the iteration is already close enough
to the zero. However, Newton's method may well fail to find the solution
in finite as well as in infinite precision arithmetic. This may happen,
for instance, if the initial value of the iteration is not close enough
to the solution. It is one of the main achievements of interval
mathematics that the method has been extended so that it can be used to
enclose all (single) zeros of a function in a given domain. Newton's
method reaches its final elegance and strength in form of the extended
interval Newton method. The method is globally convergent. It is locally
quadratically convergent and it never fails, not even in rounded
arithmetic. The key operation to achieve these fascinating properties is
division by an interval which contains zero. Newton's method uses this
operation to separate different zeros. The calculus of \overline[{IR} is
needed for an elegant formulation of the extended interval Newton method
in closed form.
It certainly is a laudable goal keeping the standard open for
extensions. However, Motion 35 seems to me degrading the concept of
'real interval' to the set IR and turns arithmetic of \overline{IR}\IR
into a flavour. I am not against introduction of flavours. But can't we
keep the standard open for extensions without introducing a new concept.
Reading the text of motion 35 gives me the impression that our time
limit is shifted to infinity.
In my opinion our main effort should be finishing the standard until the
end of this year more or less with what agreement has already been
reached. This does not mean that the group P1788 finishes working. We
still could go on developing flavours.
I am not against modal or Kaucher arithmetic. I studied Edgar Kaucher's
thesis again and again during recent weeks and I am sure that it will
take quite some time to reach general agreement on this topic. I am
afraid we do not have this much time for being successful with the
standard.
Best wishes
Ulrich
--
Karlsruher Institut für Technologie (KIT)
Institut für Angewandte und Numerische Mathematik
D-76128 Karlsruhe, Germany
Prof. Ulrich Kulisch
Telefon: +49 721 608-42680
Fax: +49 721 608-46679
E-Mail:ulrich.kulisch@xxxxxxx
www.kit.edu
www.math.kit.edu/ianm2/~kulisch/
KIT - Universität des Landes Baden-Württemberg
und nationales Großforschungszentrum in der
Helmholtz-Gesellschaft