You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@commons.apache.org by Thomas Neidhart <th...@gmail.com> on 2013/11/08 18:38:42 UTC
Re: [math] Re: Sparse matrices not supported anymore?
On 10/13/2013 09:41 AM, Ted Dunning wrote:
> Commons math decided not to support sparse matrices due to the difficulty
> of getting them just right.
>
> The problem is that 0 * Inf = NaN, not 0. This means that for floating
> point math, 0 * x = x is not a true identity.
>
> The problem really arises when the 0 in question could be either stored as
> a 0 or not. Not storing zeros is, of course, the hallmark and calling card
> of sparse matrices because if you assume that the zero multiplication
> identity holds, you can avoid lots of arithmetic.
>
> Unfortunately, if the other matrix or vector has Inf in it, multiplying by
> a sparse matrix where the corresponding element is missing gives a 0
> instead of NaN. Moreover, the dot product gives a value instead of NaN.
>
> This is very hard to fix and still retain the desirable speed properties of
> sparse matrices. You could imagine that you have a bitmap of all of the
> Inf values in every matrix, but keeping that bitmap up to date can
> absolutely kill performance since you have the potential for a branch in
> critical inner loops.
>
> Most sparse matrices just punt and say they are sorry in a very
> non-IEEE-754 sort of way.
>
> Commons Math has decided instead to remove sparse matrices entirely.
is there still consensus that we are going to remove the sparse
implementations with 4.0?
Thomas
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [math] Re: Sparse matrices not supported anymore?
Posted by Konstantin Berlin <kb...@gmail.com>.
+1
On Nov 8, 2013 3:28 PM, "Thomas Neidhart" <th...@gmail.com> wrote:
> On 11/08/2013 09:20 PM, Phil Steitz wrote:
> > On 11/8/13 11:59 AM, Ted Dunning wrote:
> >> On Fri, Nov 8, 2013 at 11:47 AM, Luc Maisonobe <lu...@spaceroots.org>
> wrote:
> >>
> >>>> is there still consensus that we are going to remove the sparse
> >>>> implementations with 4.0?
> >>> Well, I really think it is a pity, we should support this. But lets
> face
> >>> it: up to now we have been unable to do it properly. Sébastien who
> tried
> >>> to do something in this direction has left the project and nobody
> >>> replaced him.
> >>>
> >> I have done a fair bit of noodling and was unable to come up with a
> >> solution that is performant.
> >>
> >> The issue is that you essentially have to maintain a additional bitmask
> of
> >> exceptional values in addition to the implicit bitmask of non-zero
> >> elements. I don't see any way of determining that exceptional value
> >> bitmask short of a full scan. Moreover, the cost of propagating the
> >> exceptional value bitmask significantly changes the cost of various
> >> operations because exceptions require an OR while multiplication allows
> use
> >> of an AND. Furthermore, even after the operation itself and the
> operation
> >> on the exception bitmask are done, there needs to be another scan of the
> >> results to find new exceptional values.
> >>
> >>
> >> So the upshot is that dealing with this will cost at least a significant
> >> integer degradation in performance at no benefit relative to the normal
> >> user's expectations with regard to sparse vector operations. I say no
> >> benefit because no other package handles this sort of issue so users are
> >> very used to imprecise handling of exceptional values.
> >>
> > So why not just "doc and punt" - document the deficiencies that we
> > know about and the fact that we are not going to try to "fix" them
> > (which, IIUC is what other packages do)?
>
> +1, I think removing the sparse matrix implementations w/o an
> alternative will leave a lot of users quite puzzled.
>
> Thomas
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
> For additional commands, e-mail: dev-help@commons.apache.org
>
>
Re: [math] Re: Sparse matrices not supported anymore?
Posted by Thomas Neidhart <th...@gmail.com>.
On 11/08/2013 09:20 PM, Phil Steitz wrote:
> On 11/8/13 11:59 AM, Ted Dunning wrote:
>> On Fri, Nov 8, 2013 at 11:47 AM, Luc Maisonobe <lu...@spaceroots.org> wrote:
>>
>>>> is there still consensus that we are going to remove the sparse
>>>> implementations with 4.0?
>>> Well, I really think it is a pity, we should support this. But lets face
>>> it: up to now we have been unable to do it properly. Sébastien who tried
>>> to do something in this direction has left the project and nobody
>>> replaced him.
>>>
>> I have done a fair bit of noodling and was unable to come up with a
>> solution that is performant.
>>
>> The issue is that you essentially have to maintain a additional bitmask of
>> exceptional values in addition to the implicit bitmask of non-zero
>> elements. I don't see any way of determining that exceptional value
>> bitmask short of a full scan. Moreover, the cost of propagating the
>> exceptional value bitmask significantly changes the cost of various
>> operations because exceptions require an OR while multiplication allows use
>> of an AND. Furthermore, even after the operation itself and the operation
>> on the exception bitmask are done, there needs to be another scan of the
>> results to find new exceptional values.
>>
>>
>> So the upshot is that dealing with this will cost at least a significant
>> integer degradation in performance at no benefit relative to the normal
>> user's expectations with regard to sparse vector operations. I say no
>> benefit because no other package handles this sort of issue so users are
>> very used to imprecise handling of exceptional values.
>>
> So why not just "doc and punt" - document the deficiencies that we
> know about and the fact that we are not going to try to "fix" them
> (which, IIUC is what other packages do)?
+1, I think removing the sparse matrix implementations w/o an
alternative will leave a lot of users quite puzzled.
Thomas
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [math] Re: Sparse matrices not supported anymore?
Posted by Ted Dunning <te...@gmail.com>.
On Fri, Nov 8, 2013 at 12:20 PM, Phil Steitz <ph...@gmail.com> wrote:
> > So the upshot is that dealing with this will cost at least a significant
> > integer degradation in performance at no benefit relative to the normal
> > user's expectations with regard to sparse vector operations. I say no
> > benefit because no other package handles this sort of issue so users are
> > very used to imprecise handling of exceptional values.
> >
> So why not just "doc and punt" - document the deficiencies that we
> know about and the fact that we are not going to try to "fix" them
> (which, IIUC is what other packages do)?
>
Grand idea.
Got shot down last time the topic came up.
The argument was "CM will not accept philosophically wrong answers in any
form even if the rest of the world thinks that speed is worth the slightly
academic problem"
Re: [math] Re: Sparse matrices not supported anymore?
Posted by Phil Steitz <ph...@gmail.com>.
On 11/8/13 11:59 AM, Ted Dunning wrote:
> On Fri, Nov 8, 2013 at 11:47 AM, Luc Maisonobe <lu...@spaceroots.org> wrote:
>
>>> is there still consensus that we are going to remove the sparse
>>> implementations with 4.0?
>> Well, I really think it is a pity, we should support this. But lets face
>> it: up to now we have been unable to do it properly. Sébastien who tried
>> to do something in this direction has left the project and nobody
>> replaced him.
>>
> I have done a fair bit of noodling and was unable to come up with a
> solution that is performant.
>
> The issue is that you essentially have to maintain a additional bitmask of
> exceptional values in addition to the implicit bitmask of non-zero
> elements. I don't see any way of determining that exceptional value
> bitmask short of a full scan. Moreover, the cost of propagating the
> exceptional value bitmask significantly changes the cost of various
> operations because exceptions require an OR while multiplication allows use
> of an AND. Furthermore, even after the operation itself and the operation
> on the exception bitmask are done, there needs to be another scan of the
> results to find new exceptional values.
>
>
> So the upshot is that dealing with this will cost at least a significant
> integer degradation in performance at no benefit relative to the normal
> user's expectations with regard to sparse vector operations. I say no
> benefit because no other package handles this sort of issue so users are
> very used to imprecise handling of exceptional values.
>
So why not just "doc and punt" - document the deficiencies that we
know about and the fact that we are not going to try to "fix" them
(which, IIUC is what other packages do)?
Phil
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [math] Re: Sparse matrices not supported anymore?
Posted by Ted Dunning <te...@gmail.com>.
On Fri, Nov 8, 2013 at 11:47 AM, Luc Maisonobe <lu...@spaceroots.org> wrote:
> > is there still consensus that we are going to remove the sparse
> > implementations with 4.0?
>
> Well, I really think it is a pity, we should support this. But lets face
> it: up to now we have been unable to do it properly. Sébastien who tried
> to do something in this direction has left the project and nobody
> replaced him.
>
I have done a fair bit of noodling and was unable to come up with a
solution that is performant.
The issue is that you essentially have to maintain a additional bitmask of
exceptional values in addition to the implicit bitmask of non-zero
elements. I don't see any way of determining that exceptional value
bitmask short of a full scan. Moreover, the cost of propagating the
exceptional value bitmask significantly changes the cost of various
operations because exceptions require an OR while multiplication allows use
of an AND. Furthermore, even after the operation itself and the operation
on the exception bitmask are done, there needs to be another scan of the
results to find new exceptional values.
So the upshot is that dealing with this will cost at least a significant
integer degradation in performance at no benefit relative to the normal
user's expectations with regard to sparse vector operations. I say no
benefit because no other package handles this sort of issue so users are
very used to imprecise handling of exceptional values.
Re: [math] Re: Sparse matrices not supported anymore?
Posted by Luc Maisonobe <lu...@spaceroots.org>.
Le 08/11/2013 18:38, Thomas Neidhart a écrit :
> On 10/13/2013 09:41 AM, Ted Dunning wrote:
>> Commons math decided not to support sparse matrices due to the difficulty
>> of getting them just right.
>>
>> The problem is that 0 * Inf = NaN, not 0. This means that for floating
>> point math, 0 * x = x is not a true identity.
>>
>> The problem really arises when the 0 in question could be either stored as
>> a 0 or not. Not storing zeros is, of course, the hallmark and calling card
>> of sparse matrices because if you assume that the zero multiplication
>> identity holds, you can avoid lots of arithmetic.
>>
>> Unfortunately, if the other matrix or vector has Inf in it, multiplying by
>> a sparse matrix where the corresponding element is missing gives a 0
>> instead of NaN. Moreover, the dot product gives a value instead of NaN.
>>
>> This is very hard to fix and still retain the desirable speed properties of
>> sparse matrices. You could imagine that you have a bitmap of all of the
>> Inf values in every matrix, but keeping that bitmap up to date can
>> absolutely kill performance since you have the potential for a branch in
>> critical inner loops.
>>
>> Most sparse matrices just punt and say they are sorry in a very
>> non-IEEE-754 sort of way.
>>
>> Commons Math has decided instead to remove sparse matrices entirely.
>
> is there still consensus that we are going to remove the sparse
> implementations with 4.0?
Well, I really think it is a pity, we should support this. But lets face
it: up to now we have been unable to do it properly. Sébastien who tried
to do something in this direction has left the project and nobody
replaced him.
Luc
>
> Thomas
>
> ---------------------------------------------------------------------
> 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