Solving Inequalities with Piecewise and Floats

Doug Meade's picture

Quick, what numbers x satisfy:

abs( x-2 ) < 1

How does Maple answer this?

solve( abs( x-2 ) < 1, x );
                         RealRange(Open(0), Open(2))

Now, change the RHS to 1. (floating-point 1):

solve( abs(x-1) < 1., x );
           RealRange(1., Open(2.)), RealRange(Open(0.), Open(1.))

Of course, these two intervals can be combined to the one interval. Maple 10 did not have this problem. (I will explain what Maple 11 is doing later, I want the next paragraph to appear in the truncated version of this post.)

This issue is important for those of us trying to use Maple in the classroom. While it's not difficult to explain what is going on, the point is that this is not the mathematics I am trying to teach and these issues are a distraction.

Explanation:
The real source of the difficulty is the absolute value function - a piecewise defined function. Maple 11 correctly sees the two parts of the absolute value function. Solving the inequality for each part of the definition is the source for the two intervals:

q := convert( abs(x-2), piecewise, x );
                 q := piecewise(x < 2, 2 - x, 2 <= x, -2 + x)
seq( op(i,q), i=1..nops(q) );
                        x < 2, 2 - x, 2 <= x, -2 + x
solve( {op(1,q),op(2,q)<1.}, x );
                               {x < 2., 1. < x}
solve( {op(3,q),op(4,q)<1.}, x );
                               {x < 3., 2. <= x}

The question is why was Maple 10 able to combine these two sets but Maple 11 cannot?
Could it be because there is a gap the size of machine epsilon between Open(1.) and 1.?
If this is the case, then the definition of the absolute value function with floating point numbers is not defined for all floating-point numbers. Surely this is not what is intended.

Two additional points I want to make about this:

  1. For problems where the result does consist of more than one set, why does Maple not report the output from solve as the UNION of two sets?
  2. With all of the progress in 2D mathematics, couldn't there be a way to prettyprint intervals using standard mathematical notation?
    [I am not (yet) asking for simplified input for intervals, but why can't the output be improved?]

I look forward to any responses, suggestions, or differing opinions.

Doug

-----------------------------------------------------------------------
Prof. Douglas B. Meade      Phone:  (803) 777-6183  FAX: (803) 777-3783
Department of Mathematics   URL:    http://www.math.sc.edu/~meade/
USC, Columbia, SC 29208     E-mail: mailto:meade@math.sc.edu

Comments

Robert Israel's picture

union of RealRanges, not sets

Surely you don't literally mean the union of two sets, rather the union of two RealRanges. Thus:

> {x < 2., 1. < x} union {x < 3., 2. <= x};

{x < 2., 1. < x, x < 3., 2. <= x}

would not be good.

One also might ask why unions and intersections of RealRanges are not simplified. For example:

> RealRange(0,1) union RealRange(1,2);

`union`(RealRange(0,1),RealRange(1,2))

Neither simplify nor combine have any effect. Actually, what does work is

> OrProp(RealRange(0,1), RealRange(1,2));

RealRange(0, 2)

JacquesC's picture

Different authors, different sets of names

You are essentially exposing the fact that Maple has evolved over many years, and some object representations (like intervals) do not have a canonical representation in Maple (I know of at least 3). With no canonical representation, they really become second-class citizens, which essentially means that operations on them are done by specialized commands, which are not always so easy to fathom (as you demonstrate above).

Of course fixing this would require some changes that would not be backwards compatible. So even though this state of affairs dates from the Maple V era [when the third representation was added], it is unlikely to change. At least, it won't change until enough users scream that they would much prefer a consistent system over one that's compatible with last year's model. The real problem with that is there is a solution to that dilemma: Mathematica. It is much more consistent, and is entirely incompatible with Maple...

Then again, mathematics is still rather idiosyncratic. Mathematica's consistent syntax is rather disconcerting because it is quite unfamiliar. Maybe consistency just isn't that important?

Doug Meade's picture

not a case of stuck to maintain backward compatibility

Jacques,

I beg to differ.

The problem I reported about solving with inequalities and floats arose precisely because Maple 11 behaves different from Maple 10. So, this is a case where a change has been made and the change is NOT backward compatible.

I am starting to dig into the code for solve and RealRanges. I believe there will be more to report, soon.

Doug

---------------------------------------------------------------------
Douglas B. Meade
Math, USC, Columbia, SC 29208  E-mail: mailto:meade@math.sc.edu       
Phone:  (803) 777-6183         URL:    http://www.math.sc.edu/~meade/
JacquesC's picture

Yes, but

Your problem was indeed a new Maple 11 problem, and has been quite well addressed in the rest of this thread. My response above, on the other hand, was to Robert's post, rather than yours. What he was showing is related to multiple representations, which was the initial starting point of my message.

Doug Meade's picture

yes, RealRanges

Yes, I admit my original post did refer to both sets and RealRanges.

When I suggested that the result of solve should be the union of two sets I was talking about two mathematical sets - which Maple represents, in this case, as RealRanges. Thank you for pointing out this ambiguity in my posting.

Another question that I had, and did not include in my original post, is: how does Maple convert from the set

{ x < 2, 1 < x }

to the range

RealRange(Open(1),Open(2))

It is at this point that it would seem most likely to expect Maple to also look for combinations that can be simplified. As Robert points out, it appears this could be done with OrProp:

OrProp(RealRange(0,Open(1)), RealRange(1,2));
                               RealRange(0, 2)

Note that this slight revision of Robert's example clearly shows Maple has the ability to combine adjacent open and closed intervals as we would do by hand.

Moreover, this is not affected by floating point numbers:

OrProp(RealRange(0.,Open(1.)), RealRange(1.,2.));
                              RealRange(0., 2.)

So, it looks as though my conjecture about a floating point gap was incorrect. (What a relief!) So, now it appears there was a change between Maple 10 and 11 that omits this simplification of the results from solve.

---------------------------------------------------------------------
Douglas B. Meade
Math, USC, Columbia, SC 29208  E-mail: mailto:meade@math.sc.edu       
Phone:  (803) 777-6183         URL:    http://www.math.sc.edu/~meade/
Doug Meade's picture

problem located: RealRange_union

I believe I have found the source of the problem. Maple 11 does try to combine the two RealRanges, but fails because signum(0.) returns as a float (0.) and not an integer (0).

The code for RealRange_union looks for overlapping, or adjacent, intervals. It does this by looking at the signum of the difference of the endpoints of the ranges. In most cases, signum returns 1 or -1 (integers), but signum(0.) returns 0. (floating point).

Here is the source for RealRange_union, with some comments added:

showstat( RealRange_union );

RealRange_union := proc()
local i, j, r, r1, r2, t1, t2, lo, hi, si;
   1   if nargs < 2 or not has([args],RealRange) then
   2     return args
       elif 2 < nargs then

for more than 2 ranges, work pairwise (recursion)

   3     for i to nargs do
   4       for j from i+1 to nargs do
   5         r := traperror(procname(args[i],args[j]));
   6         if r <> lasterror and nops([r]) = 1 then
   7           return procname(op(subsop(i = r,j = NULL,[args])))
             end if
           end do
         end do;
   8     return args
       else

extract endpoints of range 1

   9     r1 := traperror(RealRange_ends(args[1]));
  10     if r1 = lasterror then
  11       return args
         end if;

extract endpoints of range 2

  12     r2 := traperror(RealRange_ends(args[2]));
  13     if r2 = lasterror then
  14       return args
         end if;
  15     if type(r1[1],Open(algebraic)) then
  16       t1 := op(1,r1[1])
         else
  17       t1 := r1[1]
         end if;

check order of left endpoints of each range

  18     if type(r2[1],Open(algebraic)) then
  19       t2 := op(1,r2[1])
         else
  20       t2 := r2[1]
         end if;
  21     if has(t1,infinity) and has(t2,infinity) then
  22       si := 1
         else
  23       si := signum(t2-t1)
         end if;
  24     if not type(si,integer) then
  25       return args
         end if;
  26     if si = -1 or si = 0 and type(r1[1],Open(algebraic)) then

reverse order of the ranges

  27       t1 := r1;
  28       r1 := r2;
  29       r2 := t1
         end if;

At this time it is known that the left endpoint of range 1 <= right endpoint of range 2.

Now, look for overlap by comparing the right endpoint of range 1 and the left endpoint of range 2.

  30     if type(r1[2],Open(algebraic)) then
  31       t1 := op(1,r1[2])
         else
  32       t1 := r1[2]
         end if;
  33     if type(r2[1],Open(algebraic)) then
  34       t2 := op(1,r2[1])
         else
  35       t2 := r2[1]
         end if;
  36     si := signum(t2-t1);

Reduction is NOT possible when:
i) t2>t1 or
ii) both ranges are open @ t1=t2
In all other cases, simply return args unchanged

  37     if not type(si,integer) then
  38       return args
         end if;
  39     if si = 1 or si = 0 and type(r1[2],Open(algebraic)) and type(r2[1],Open(algebraic)) then
  40       return args
         end if;

Finally, begin construction of the merged range. The left endpoint is easy (because of original ordering of the ranges).

  41     lo := r1[1];

The right endpoint takes more effort. (But, isn't there a better way to do this?)

  42     if type(r2[2],Open(algebraic)) then
  43       t2 := op(1,r2[2])
         else
  44       t2 := r2[2]
         end if;
  45     if has(t1,infinity) and has(t2,infinity) then
  46       si := 1
         else
  47       si := signum(t2-t1)
         end if;
  48     if not type(si,integer) then
  49       return args
         end if;
  50     if si = 1 or si = 0 and type(r1[2],Open(algebraic)) then
  51       hi := r2[2]
         else
  52       hi := r1[2]
         end if;

Final processing to handle infinity, then return the single combined range

  53     if has(lo,infinity) then
  54       lo := -infinity
         end if;
  55     if has(hi,infinity) then
  56       hi := infinity
         end if;
  57     RealRange(lo,hi)
       end if
end proc

This procedure appears to be needlessly complicated, and is certainly quite old. (This code is exactly the same as the code found in Maple 10.)

I do not completely understand the rationale for using signum and not (simple) inequalities, but I trust there is (or was) a reason for this. Maybe something with the handling of infinity or symbolic arguments?

My suggestion for fixing this routine is to replace the use of

if not type(si,integer) then

in lines 24, 37, and 48 with

if not type(convert(si,rational),integer) then

While I do not have the time to completely rewrite this procedure, I can see that it would benefit from

  • replacement of traperror/lasterror to try ... catch ... end try (lines 9-11 and 12-14)
  • use of multiple assignments to interchange two quantities (lines 27-29)
  • and typematch and patmatch

Of course, a full solution to this problem will involve a comprehensive look at RealRange_intersect and all of the related routines. I hope this diagnosis of the problem is helpful to someone who can implement a complete solution.

Doug

---------------------------------------------------------------------
Douglas B. Meade
Math, USC, Columbia, SC 29208  E-mail: mailto:meade@math.sc.edu       
Phone:  (803) 777-6183         URL:    http://www.math.sc.edu/~meade/

it's useful

This is useful Doug. By that I mean it's very useful to have straighforward examples which show what can be improved.

That routine, RealRange_union, dates from about 1993. The bits about infinity were added at some later date.

It's clear that you enjoyed analyzing it. Another thing worth examining might be whether the use of eval@subs is really necessary in RealRange_ends.

Dave Linder
Mathematical Software, Maplesoft

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.
}