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

Re: discussion period begins, until Jan. 26: "natural interval extension": friendly amendment to M001.02



Dear Mr. Kulisch,

it's hard for me to understand your criticism regarding the standard
document. Your main objections—as far as I understand—are that the EDP
should be a required operation and exceptions from IEEE 754 shall not be
included.

The standard document recommends the EDP for computation of (already
required) reduction operations. When implementing the standard I found
the EDP the easiest and most efficient way of implementing the reduction
operations. So I have implemented EDP anyway. I must admit that it is
implemented in software and I would have preferred hardware support, but
that hopefully gets addressed by other people who implement the standard
in hardware and who will face the same problems that I did. There is
high chance that they will choose to use EDP as well.

On 22.01.2016 16:46, Ulrich Kulisch wrote:
> As an example let's consider the central task of interval analysis,
> computing close bounds for the solution of a system of linear equations.
> 
> First an approximate solution is computed. Then the Kravczyk-operator
> with epsilon-inflation for computig a verified enclosure is applied. If
> the system has a large condition number the verificaion step fails. But
> in contrast to conventional floating-point arithmetic the routine
> detects this. Then it automatically calls a more powerful operator which
> I call the Rump-operator in my book. It has been shown by Rump, Oishi,
> Ogita and Tanabe that this process even for very ill-conditioned
> problems always leads to a highly accurate verified enclosure.
> 
> A look at the details (Chapter 9 in my book /Computer Arithmetic and
> Validity/ for instance) shows that the essential ingredient of the
> entire process is an EDP. Recently two students at Berkeley showed that
> the EDP can be computed in 1/6 of the time that is needed for computing
> a possibly wrong result in conventional floating-point arithmetic. So it
> is really worth fighting to get this extremely useful and fast operation
> standardized.

I have migrated this algorithm from C-XSC. As already indicated above, I
have made use of EDP. In particular I have integrated EDP into Octave
functions “dot (X, Y)” and “X * Y” (matrix multiplication) as well. If
you know Octave, which is a free replacement for Matlab, you will
recognize that the EDP thereby became an integral part of the
implementation: Computations with matrices are very common in that language.

On the other hand, it highly depends on your use case whether you need
these matrix operations and the EDP. The standard document does not
emphasize usage of interval vectors or interval matrices. Therefore it
is no surprise that the EDP and other operations on interval vectors are
missing. However, the standard document provides enough information to
consistently implement these functions where needed.


Regarding the other topic: Which exceptions does the standard pull in
from IEEE 754? The standard defines a NaI object, which is the result of
interval constructors on invalid input. It propagates through arithmetic
operations, but does not trigger exceptions like 1/0 = NaN would do. The
interval arithmetic is exception free, e. g., [1]/[0] = [Empty].

In addition the standard guides those who chose to use IEEE 754 formats
for implementation. This is good, because these formats are very common
today. Again, this does not pull in exceptions from IEEE 754.
Contrariwise, the decoration system of IEEE Std 1788-2015 has no global
flags and does not interrupt the flow of computation.

> By the way: In my book interval arithmetic is developed over the real
> and floating-point numbers. This leads to an exception-free, closed
> calculus. It avoids all the exceptions of the IEEE 754 standard being
> pulled into interval arithmetic.

Could you please clarify where the arithmetic of IEEE Std 1788-2015
differs from what is developed in your book? In my eyes they are the same.

Best regards
Oliver Heimlich