commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Bill Barker" <billwbar...@verizon.net>
Subject Re: [math] Problems with sparse implementations of RealVector
Date Tue, 19 Jun 2012 07:30:59 GMT


-----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.

>Luc
>
>
> Any better idea?
> Thanks in advance,
> Sébastien
>
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
> For additional commands, e-mail: dev-help@commons.apache.org
>
>


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


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


Mime
View raw message