Re: modal interval
Nate Hayes schrieb:
Arnold Neumaier wrote:
Nate Hayes wrote:
Arnold Neumaier wrote:
Modal techniques can possibly evaluate equivalent range enclosures
in a slightly more automatic or faster way, given appropriate
hardware support.
I'm glad to hear you admit that much, Arnold.
... with the stated qualifications;
- possibly,
- given appropriate hardware support,
- it would have to be demonstrated on a realistic benchmark
At the moment, it is only based on hearsay from you, without any
support by evidence. The evidence quoted below is spurious, since it
beats only a straw man.
I think it is realistic to estimate that one interval operation can be
computed in about the same time as one floating-point operation. For
example, in the paper
http://grouper.ieee.org/groups/1788/Material/KirchnerKulisch-
HardwareSupport.pdf
Ulrich says:
"The circuits described in this paper show that with modest additional
hardware costs interval arithmetic can be made almost as fast as simple
foating-point arithmetic."
SIMD instructions on modern Intel and AMD chips give us a reasonable guide
of what to expect.
Nate Hayes wrote:
Arnold Neumaier wrote:
It is impossible to know undisclosed, nowhere detailed methods.
To argue with such confidential knowledge may be good marketing,
but is against the scientific spirit.
...
But to claim this as a scientific fact, it would have to be
demonstrated on a realistic benchmark, or at least on a nontrivial,
realistic example.
Chapter 6 of my paper gives one such example. It is simple example,
but not
trivial and not insignificant, since Beziers, b-splines and NURBS
form foundation of global industry in fields such as CAD,
engineering, desktop publishing and computer graphics.
You compare it only with ordinary interval evaluation,
which is easy to beat. Compared to this, most other methods look good.
It is like praising a new optimization method because it is faster
than steepest descent.
For the same computational effort as classical arithmetic, the improvement
is order of magnitude (or more) in terms of quality of the range enclosure
bounds.
But you are bearting a straw man by comparing against the most naive
algorithm available.
As cited in my survey paper, there are much better interval algorithms
available for Bezier curve enclosure (even ignoring the linearInt()
approach), which surpass the accuracy of your method. You lose
accuracy due to interval dependence in the recursive part of the algorithm.
To convince others of the superiority of modal techniques, you need to
compare against the state of the art, not against the simpleton.
But compare it against the use of monotonicity methods, as given in
my paper, and you'll find no advantage anymore. (I think, the
monotonicity methods had even a 2% advantage.)
That example in your paper, i.e., the linearInt() function from Vienna
Proposal, is simply the component-wise form of the modal interval arithmetic
operations
A+U*(B-Dual(A)).
Well, you say, monotonicity methods plus directed rounding are nothing
else than modal intervals in disguise, but this is in the eye of the
beholder.
With the same right one can say, modal intervals (as used for range
computations) are nothing but monotonicity methods plus directed
rounding in disguise, which would mean that modal intervals are
not needed at all since the traditional methods (monotonicity,
directed rounding) are sufficient to reproduce the modal results.
From my perspective, it is about computational efficiency and speed,
provided the right hardware is available. For example, (x*y)/(x+y+1) can be
computed with classical interval arithmetic for X=[0,2] and Y=[0,2] in 4
interval operations to obtain the pessimistic range enclosure [0,4].
Endpoint analysis
[(inf(x)*inf(y))/(inf(x)+inf(y)+1),(sup(x)*sup(y))/(sup(x)+sup(y)+1)]
computes the optimal range enclosure [0,0.8] in 8 floating-point operations.
But if we assume that two directed floatng-point operations on a
directed processor, as suggested in my paper, can be computed
in about the same time as one floating-point operation, which is
possible using circuitrtry of complexity comparable to a modal interval
processor, and gives a more widely applicable device, the cost for the
optimal range enclosure goes down to 4 floating-point operations.
Thus there is no need for a modal interval processor to get the speed
advantage.
It thus all depends on the point of view....
If we assume one interval operation on an interval processor can be computed
in about the same time as one floating-point operation, then the interval
processor computes the range enclosure twice as fast but over 4 times more
pessimistically.
again, this holds only assuming the simpleton approach.
So an end-user can have fast or optimal result, but not both.
An end user with appropriate hardware support can have both.
The modal approach also needs appropriate hardware support;
so your comparison of one method without extra hardware support
against your method with extra hardware support is unfair.
A modal interval processor can compute
(X*Y)/(Dual(X)+Dual(Y)+1)=[0,0.8]
in 4 interval operations. So it computes the optimal range enclosure of the
endpoint analysis in the same amount of time as the classical interval
processor (which does not compute an optimal result).
Even with more right - for to apply modal techniques, one needs
total monotonicity, while the endpoint method can work with simple
monotonicity. Thus the latter is of broader applicability.
There can still be benefit in these cases. One example in your paper is
(x*y-1)/(x+y+1) for x,y >= 0, which is not totally monotonic. But we can
factor into the equivalent expression (x*y)/(x+y+1)-1/(x+y+1) and compute
the optimal range enclosure
(X*Y)/(Dual(X)+Dual(Y)+1)-1/(X+Y+1)=[-1,0.6]
on a modal interval processor in the same time as 8 floating-point
operations.
At the cost of 8 modal operations on a dedicated modal processor,
which must be comparted to the cost of 5 paired directed operations
on a dedicated directed processor.
Thus the modal way is now 60% slower, without any gain in accuracy!
To compute the optimal range enclosure with endpoint analysis
requires 10 floating-point operations. So computation on a modal processor
is still faster.
Only if you assume the unfair advantage that the modal calculation has
access to special hardware while the monotonicity method is not granted
that privilege.
I therefore don't find your argumentation convincing.
Arnold Neumaier