Re: modal interval
Nate Hayes schrieb:
Arnold Neumaier wrote:
Nate Hayes schrieb:
Arnold Neumaier wrote:
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.
There are not much details on this algorithm in your paper,
The details are in the references quoted on p.9 of my survey.
Moreover, the second paragraph there gives enough details for an
alternative algorithm that should outperform yours for the enclosure
of a whole Bezier curve, if implemented well enough (re-use information
for adjacent intervals).
but it appears
to require change of basis of the control points. In doing so, interval
dependency can occur that defeats the purpose by causing the interval width
of the control points to increase. It also requires extra computational
effort to change basis, since applications in CAD, computer graphics and
desktop publishing specify the curves in terms of control points.
One of the main advantages of the interval de Casteljau and interval de Boor
algorithms is they can be easily implemented in a deeply pipelined hardware
circuit that requires no branching conditions, and the algorithms operate
directly on the control points.
The algorithm of the second paragraph only involves point de Casteljau
and de Boor algorithms, which are surely as well implementable.
To convince others of the superiority of modal techniques, you need to
compare against the state of the art, not against the simpleton.
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.
This essentially describes a SIMD register that allows rounding in different
directions. It is not more general, because branching conditions are often
required (as in the linearInt() formula), so it will not work for these
cases. Some other special hardware circuit will be required, or else there
will be speed to be suffered because of the branching conditions.
Thus there is no need for a modal interval processor to get the speed
advantage.
It thus all depends on the point of view....
As mentioned above, the linearInt() formula is a simple example where this
approach does not work.
The algorithm of the second paragraph on p.9 of my survey,
does not have any branching, and makes no use of linearInt(),
but only of simple monotonicity.
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!
In this case extra operations in the above example are pipelined and won't
cause processor stalls. With the paired processor approach, the loss of
speed is potentially much more severe when branching conditions are
required, as in the linearInt() formula.
We were discussing a particular example where there is no such stalling.
Moreover, even in linearInt(), the stalling can be prevented in a
similar way as your modal processor prevents stalling in the branches
that the traditional formulation of modal arithmetic entails.
Apply the same ingenuity that you applied to the modal processor to
a directed rounding processor, and you get a more flexible tool at
a very similar hardware cost.
It is also worth mentioning that the paired processor approach is not truly
an "interval processor." IMHO, if one goal of 1788 is to provide incentive
for hardware vendors to manufacture interval processors, this route is
counter-productive to that goal.
A processor with two pipelines for directed rounding in each direction
can easily be adapted to allow both directed rounding calculations and
an interval arithmetic (which consists mostly of the latter). The
resulting processer is not more complex than a modal processor.
Arnold Neumaier