commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Sébastien Brisard <sebastien.bris...@m4x.org>
Subject Re: [math] Problems with sparse implementations of RealVector
Date Tue, 19 Jun 2012 08:33:23 GMT
Hi Bill,

2012/6/19 Bill Barker <billwbarker@verizon.net>:
>
>
> -----Original Message----- From: Luc Maisonobe
> Sent: Monday, June 18, 2012 1:40 AM
> To: Commons Developers List
> Subject: Re: [math] Problems with sparse implementations of RealVector
>
>
>> Hi Sébastien,
>>
>> Le 18/06/2012 08:11, Sébastien Brisard a écrit :
>>>
>>> Dear all,
>>>
>>> in this thread,
>>> http://markmail.org/thread/hhvm6wv3d3uhkwqs
>>> we had an interesting discussion on a bug which was revealed by
>>> abstract unit tests on all implementations of RealVector. It turns out
>>> that the bug is more far-reaching than we initially thought, and I
>>> would like to make sure that it has been brought to everyone's
>>> attention (as the subject of the previous thread was pretty cryptic).
>>>
>>> So here goes. In RealVector, we provide ebeMultiply(RealVector) and
>>> ebeDivide(RealVector). Also, in sparse implementations of RealVector,
>>> zero entries are not stored. This is all very well, but for the fact
>>> that 0.0 is actually signed in Java. The sign of zero is effectively
>>> lost in OpenMapRealVector. This affects the correctness of the
>>> returned values of ebeMulltiply() and ebeDivide()
>>>
>>> 1. For ebeMultiply()
>>>        final RealVector v1 = new ArrayRealVector(new double[] { 1d });
>>>        final RealVector v2 = new OpenMapRealVector(new double[] { -0d });
>>>        final RealVector w = v1.ebeMultiply(v2);
>>>        System.out.println(1d / w.getEntry(0));
>>>
>>> prints Infinity, instead of -Infinity (because the sign is lost in
>>> v2). This means that w holds +0d instead of -0d.
>>>
>>> 2. For ebeDivide()
>>>        final RealVector v1 = new ArrayRealVector(new double[] { 1d });
>>>        final RealVector v2 = new OpenMapRealVector(new double[] { -0d });
>>>        final RealVector w = v1.ebeDivide(v2);
>>>        System.out.println(w.getEntry(0));
>>>
>>> prints Infinity, instead of -Infinity. For this last bug, Gilles
>>> suggested the following fix
>>>
>>>>
>>>>  public OpenMapRealVector ebeDivide(OpenMapRealVector v) {
>>>>   if (v.getDefaultEntry() == 0) {
>>>>     throw new ZeroException();
>>>>   }
>>>>
>>>>   // ...
>>>>  }
>>>>
>>>
>>> which was indeed no big deal, since the exception occured only when
>>> the expected entry should have been + or -Infinity (which means that
>>> the calculation had effectively failed).
>>>
>>> However, this fix is not the end of the story, because it should be
>>> applied to *any* implementation of RealVector.ebeDivide, as long as
>>> the provided argument is an OpenMapRealVector. This makes things
>>> cumbersome. Also, other implementations of RealVector (not only
>>> OpenMapRealVector) might be affected by the same limitation. In my
>>> view, this would require the definition of a new abstract method in
>>> RealVector
>>> protected boolean preservesSignOfZeroEntries()
>>> which returns true if the sign of zero entries can be reliably
>>> retrieve from this vector. Then, for each implementation of
>>> ebeMultiply and ebeDivide,, we should test for
>>> preservesSignOfZeroEntries(), and handle the boundary cases
>>> accordingly.
>>>
>>> The question is then: how should the boundary case be handled in the
>>> ebeMultiply example? In this case, the expected value is perfectly
>>> valid, and throwing an exception would effectively stop a computation
>>> which is not yet in failed state.  I would be tempted to quietly
>>> accept operations like : any double * (zero with undecidable sign).
>>> The returned value would be zero with undecidable sign (remember that
>>> the sign of zero is only used to compute (any double) / (signed
>>> zero)). But then, preservesSignOfZeroEntries() must be specified at
>>> construction time, because even ArrayRealVector might in some
>>> circumstances end up with zero entries with undecidable sign... This
>>> quickly gets very complicated!
>>>
>>> I think there is no satisfactory implementation of ebeMultiply and
>>> ebeDivide, and I would go as far as deprecate them. Users who need to
>>> perform these operations can always use visitors to do so efficiently
>>> (if not in an absolute fool-proof way).
>>
>>
>> This sound good to me. I am not a big fan of all the ebe methods
>> (despite I think I am the one who implemented them, from a user
>> request). I also would be glad if we removed most or even all of the map
>> methods.
>>
>
> The ebe methods aren't all that interesting, and with the new visitor
> pattern they can be implemented by the user.  Also, the users of
> SparseVector really won't care what value of +-infinity and/or NaN is stored
> and would probably just prefer that an exception is thrown if this case is
> detected.
>
I agree. I miss the good old "division by zero" error...
Sébastien


---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org


Mime
View raw message