| Thread Links | Date Links | ||||
|---|---|---|---|---|---|
| Thread Prev | Thread Next | Thread Index | Date Prev | Date Next | Date Index |
Arnold Neumaier schrieb:
In the proposal "exact" really means exact (not a single bit is lost), while in the prargraph above 'exact' means computing the least upper floating-point interval bound.R. Baker Kearfott wrote:A motion to include an exact dot product in the interval arithmetic standard has been made and seconded. Therefore, the three week discussion period begins, to end after Wednesday, October 27.1. I strongly support an exact sum, 1-norm, 2-norm, and dot product that takes real vector arguments and returns the tightest interval result(as in Section 5.1 the Vienna Proposal, with the norms handled similarly upon requests in a previous discussion).
This is correct for 'exact'. But the IFIP Working Group letter requests an "exact" dot product as support for long interval arithmetic (for details see [6] or [9]). Long interval arihtmetic opens a new area of applications for interval arithmetic. I give a few examples:2. I find it acceptable to do this via a complete format of very long floats as proposed in the motion, but would very much prefer if this is not made mandatory but left to the implementor, since, for actual applications, the main gain for the user is the form specified in the Vienna Proposal, and there are lots of algorithms that achieve this efficiently without a complete format.
The Krawczyk operator frequently is used to compute a verified enclosure for the solution of a system of linear equations. But for ill conditioned problems (take the Hilbert matrices of dimension larger than 11) the Krawczyk operator fails to find the solution. In such cases a more powerful operator (called the Rump operator in [9]) solves the problem. In its extended form the Rump operator can be used to compute a verified solution even for extemely ill conditioned problems, see [11]. The Rump operator uses the "exact" dot product.
Another very nice example is given in [7], an iteration with the logistic equation. Double precision floaint-point or interval arithmetic totally fail (no correct digit) after 30 iterations while long interval arithmetic after 2790 iterations still computes correct digits of a guaranteed enclosure. Long interval arithmetic allows computing highly accurate bounds for real arithmetic expressions.
If an "exact" dot product is available, Section 3 of the proposal is a trivial consequence and it could be dropped. It was added in order to demonstrate that in a pure interval computation (which is free of exceptions) also computing the interval dot product is free of exceptions. All the exceptions that had to be dealt with in section "2.2.1 Convert" of the proposal do not occur in a pure interval computation. A pure interval computation only makes use of non exceptional flaoting-point numbers. In contrast to this an "exact" dot product, if it is based on IEEE 754, has to consider the IEEE 754 exceptions also.3. I see no need at all for corresponding versions of the optimal dot product etc. for interval input. The reason is that real sums or inner products easily have lots of cancellation under addition when the sign differ, while uncertainties in intervals add up, no matter which signs the operand have. Thus the accuracy to be gained by a highly accurate summation is usuallyonly a small fraction of the width that is incuured by summing the interval widths.I'd appreciate to know about applications - if there are any - where an interval dot product would be essential for good performance.In the spirit of simplicity I therefore suggest that only the real to interval case of the motion is supported, and not the interval to interval version, i.e., Section 3 of the motion text is dropped.
Best regards Ulrich Kulisch
Arnold Neumaier