Re: Bisection methods: a use-case example

[Ian McIntosh <ianm@xxxxxxxxxx>]

One solution is to define multiple functions:
- midpoint ( ) which would return the mathematical midpoint, or a NaN if either endpoint is Infinite (or if the interval is empty)
- midpoint_or_zero ( ) which would return the mathematical midpoint, or a zero if either endpoint is Infinite (or if the interval is empty)
- median_splitpoint ( ) which would return a non-NaN split point equal to or approximately equal to the median (or NaN if the interval is empty)
- log_splitpoint ( ) which would return a non-NaN split point approximately equal to the median exponent (or NaN if the interval is empty)
- mean_splitpoint ( ) which would return a non-NaN split point approximately equal to the mean (or NaN if the interval is empty)
- sqrt_splitpoint ( ) which would return a non-NaN split point approximately equal to the sqrt (or NaN if the interval is empty)
and any other useful ones, so that Dick, Jane, Sally and Spot could each choose the most appropriate for their application.

- Ian McIntosh IBM Canada Lab Compiler Back End Support and Development


Ralph Baker Kearfott ---05/27/2012 08:34:18 AM---Nate, I see your point. I am wondering, however, whether or not

From:	Ralph Baker Kearfott <rbk@xxxxxxxxxxxx>
To:	Ian McIntosh/Toronto/IBM@IBMCA
Date:	05/27/2012 08:34 AM
Subject:	Re: Bisection methods: a use-case example

---

Nate,

I see your point.  I am wondering, however, whether or not
defining midpoint([1,+Inf]) = NaN is a necessary consequence
of the midpoint of an infinite interval being undefined at
level 1 or not, or whether or not the definition of midpoint
for such intervals depends on interpreting the upper bound
as Inf or omega.  It seems that, if we decide that midpoint
should take on a finite value in such cases, we can, in principle,
regardless of whether or not we view the upper bound as
Inf or omega, set it to any value.  In your example, I might
suggest sqrt(1*REALMAX).

If we do specify a particular finite value (which I guess is
somewhat arbitrary, but to a certain extent, isn't standardization
deciding on a common way of doing arbitrary things?)  I suspect
there will be users of the standard for whom the standard choice
is not appropriate.  Such a user, say, Sarita, would then need to
write her own routine, although Sally might not.

So, which choice do we make to minimize the total inconvenience
over all users?

Baker

On 05/26/2012 09:47 AM, Nate Hayes wrote:
> John, Michel, P1788,
>
> To illustrate things from my perspective a little more clearly, here is a
> use-case example:
>
> Case A: No Overflow
> ----------------------
>
> In this scenario, the midpoint of an unbounded interval is undefined at
> Level 1, and at Level 2 it returns NaN. So we have, e.g., a P1788 midpoint
> operation like this:
>
> midpoint([1,5]) = 3
> midpoint([1,+Inf]) = NaN
>
> and the Interval Newton algorithm (14) in section 3.2.2 generates NaNs
> instead of finding the solution [1.49998,1.50003].
>
> So our user Sally instead writes a "pragmatic" midpoint operation called
> "midpoint2" that is undefined at Level 1 for an unbounded input but returns
> REALMAX at Level 2 anyways; Sally's midpoint2 operation gives, e.g.,
>
> midpoint2([1,5]) = 3
> midpoint2([1,+Inf]) = REALMAX
>
> Sally likes her midpoint2 better than the P1788 midpoint operation because
> hers allows (14) to find the solution, so this is what she uses.
>
> I think everyone agrees Sally did something really pragmatic, but one might
> ask the question: is Sally really following the standard or is she just
> working around it? Technically, her midpoint2 is undefined at Level 1 for
> the input [1,+Inf] just like the P1788 midpoint operation is. If the P1788
> midpoint operation returns NaN at Level 2 to avoid contradicting the Level 1
> definition, then why is the user's operation not also a contradiction? Just
> because the user gives the operation a different name? In other words, does
> changing the name of an operation also change the mathematical defintion of
> the operation?
>
> Not that I blame Sally. How many other users will re-invent midpoint2 like
> Sally did? And who is going to end up using the P1788 midpoint operation in
> this scenario, anyway? Anybody?
>
>
>
> Case B: Overflow
> ------------------
>
> In this scenario, the midpoint of an unbounded interval is undefined at
> Level 1 and at Level 2. However, the unbounded intervals are re-interpreted
> as overflow so we have, e.g., a P1788 midpoint operation defined at Level 1a
> and Level 2 like this:
>
> midpoint([1,5]) = 3
> midpoint([1,+omega]) = REALMAX
>
> and the Interval Newton algorithm (14) in section 3.2.2 finds the solution
> [1.49998,1.50003]. So Sally likes this midpoint; especially since it
> might be implemented in a P1788 interval processor and be really fast!
>
> Sally's colleague, Harry, knows that for this particular numerical problem,
> the Interval Newton will find the solution in only 14 total iterations if he
> uses smedian instead of midpoint. So Harry designs a smedian bisection
> routine that, like the P1788 midpoint operation, is defined at both Level 1a
> and Level 2 on overflow according to Table 1, i.e.,
>
> smedian([1,5]) = 2.315
> smedian([1,+omega]) = h
>
> where h = REALMAX at Level 2, and he uses this instead.
>
> Nate
>


-- 

---------------------------------------------------------------
Ralph Baker Kearfott,   rbk@xxxxxxxxxxxxx   (337) 482-5346 (fax)
(337) 482-5270 (work)                     (337) 993-1827 (home)
URL: http://interval.louisiana.edu/kearfott.html
Department of Mathematics, University of Louisiana at Lafayette
(Room 217 Maxim D. Doucet Hall, 1403 Johnston Street)
Box 4-1010, Lafayette, LA 70504-1010, USA
---------------------------------------------------------------