Re: modal interval
Arnold Neumaier wrote:
> 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.
There are not much details on this algorithm in your paper, 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.
>
> 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.
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.
>
>
>> 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.
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.
Nate