Re: About diagonal matrices

[Jaroslav Hajek]

On Sun, Mar 1, 2009 at 10:40 PM, Daniel J Sebald <address@hidden> wrote:
> Jaroslav Hajek wrote:
>>
>> On Sun, Mar 1, 2009 at 9:16 PM, Daniel J Sebald <address@hidden>
>> wrote:
>>
>>> Jaroslav Hajek wrote:
>>>
>>>> On Sun, Mar 1, 2009 at 8:23 PM, Daniel J Sebald <address@hidden>
>>>> wrote:
>>>>
>>>>
>>>>> dbateman wrote:
>>>>>
>>>>>
>>>>>
>>>>>> Well I'm finally somewhere I can write an e-mail from easily, though I
>>>>>> haven't had the time to reread the thread. The issue I considered in
>>>>>> the
>>>>>> past like this was operations like "speye(n) .^ 0" or "speye(n) ./ 0"
>>>>>> where
>>>>>> the 0.^0 and 0./0 terms of the matrix should create a NaN in the
>>>>>> resulting
>>>>>> matrix I hadn't considered the "speye(n) OP NaN" but didn't and don't
>>>>>> yet
>>>>>> see why it should be different if the NaN is pre-existing rather than
>>>>>> created by the binary operation, otherwise the NaN values won't
>>>>>> propagate
>>>>>> and in fact might very likely disappear. You seem to think, and have
>>>>>> convince John that disappearing NaN's are a good thing so I'll try to
>>>>>> reread
>>>>>> the thread and respond again later on.
>>>>>
>>>>> I think a "default sparse value" solves this, no matter what one thinks
>>>>> the
>>>>> defined behavior should be.  Call the indeces assigned the default
>>>>> value
>>>>> the
>>>>> "sparse set".  The sparse set could be NaN, while assigned values could
>>>>> also
>>>>> happen to be NaN.
>>>>
>>>>
>>>> No, it doesn't. At least not completely - just the simple cases. See
>>>> my previous examples about this. And it would make the sparse
>>>> operations more complicated and probably less efficient.
>>>> You are, obviously, free to propose a detailed implementation. But
>>>> please be more specific.
>>>
>>> Say I define a sparse matrix where indeces (i,j) in S are zero.  Call S
>>> the
>>> sparse set.  I.e.,
>>> M(i,j) = 0 for (i,j) in S
>>>      m_i,j otherwise
>>>
>>> Now, do an operation on M (something simple so we can avoid the issues of
>>> set operations across sparse matrices... I know, that's where all the
>>> work
>>> is), say M/0.  Then
>>>
>>> M(i,j)/0 = Nan for (i,j) in S
>>>        m_i,j / 0 otherwise
>>>
>>> We've kept track of the sparse set, so we still know what this.  Little
>>> has
>>> changed, assigned from assigning the sparse set a value.  Correct?
>>>
>>
>>
>> Yes. That's the simple case. Now please describe how to multiply two
>> sparse matrices.
>> Or, to get you something simple, how you multiply a full * sparse matrix.
>
> These are all judgements and why I said "no matter how one defines", but I'd
> probably rule out the mixture of the two and think of it as either full is
> converted to sparse or vice versa.  Say S is a sparse matrix and F is a full
> matrix.  I'm gathering that you feel
>
> sparse(F) * S
>
> and
>
> F * full(S)
>
> don't necessarily yield the same result.  I can see that being useful.
>

If they don't, then probably the whole effort is just pointless - what
problem does it solve?. But let's say it's OK. I was just asking how
do you imagine the implementation of sparse (with your general default
sparse value) * full matrix product.
Or sparse * sparse, with possibly two different default values. Try to
lay it down on a paper, I think you'll see it's really not that easy.
Especially if you want to catch all the possible cases with NaNs and
Infs.

>
>>> For the more general operations of two sparse sets, I proposed in a
>>> previous
>>> email to keep track of index sets.  It adds more complexity.
>>
>>
>> I'm still somewhat confused, probably. Octave indeed does keep track
>> of the sparsity pattern for sparse matrices. Otherwise, they could
>> hardly be sparse.
>
> My point has been that I'm not proposing anything too much different other
> than assigning the sparse set some value other than zero when we know its
> value isn't zero.
>
> I asked some emails back what "NNZ" means.  I think it means something like
> "number not zero".  But that is poor and limiting terminology.  I guess what
> I'm proposing is something like "number not sparse".  So instead of
>
> octave:3> speye(3)
> ans =
>
> Compressed Column Sparse (rows = 3, cols = 3, nnz = 3)
>
>  (1, 1) ->  1
>  (2, 2) ->  1
>  (3, 3) ->  1
>
> octave:4> speye(3)/0
> warning: division by zero
> ans =
>
>  Inf   NaN   NaN
>  NaN   Inf   NaN
>  NaN   NaN   Inf
>
> we would have
>
> octave:3> speye(3)
> ans =
>
> Compressed Column Sparse (rows = 3, cols = 3, nns = 3, sval=0)
>
>  (1, 1) ->  1
>  (2, 2) ->  1
>  (3, 3) ->  1
>
> octave:4> speye(3)/0
> ans =
>
> Compressed Column Sparse (rows = 3, cols = 3, nns = 3, sval=NaN)
>
>  (1, 1) ->  Inf
>  (2, 2) ->  Inf
>  (3, 3) ->  Inf
>
> Notice the subtle difference.  There is an advantage to the above notation
> going back to John's original point and what I've said above.  It may be OK
> to have operations on sparse results produce slightly different results so
> long as the user knows the underlying math was "full matrix" or "sparse
> matrix".  The result of sparse * sparse looks like above.  The result of
> full * full looks like the common result.  full * sparse would be
> sparse(full) * sparse and should look like above.
>

Yes, in this simple case, it looks nice, but it really gets more
complicated when you dive in. Besides, none of our external software
(UMFPACK) can work with such matrices.


>
>>>
>>>>> The value of the sparse matrix is when it comes time to use it in
>>>>> operations
>>>>> where a full matrix would consume the CPU.  So it does make sense to
>>>>> keep
>>>>> track of the sparse set.
>>>>>
>>>>
>>>>
>>>> Huh? I don't understand.
>>>
>>> What is the purpose of sparse sets?  Represent large matrices that are
>>> mostly zero (or some default value, I argue).  Also, when solving matrix
>>> operations or systems of equations that are sparse, much of the
>>> computations
>>> can be discarded.
>>>
>>
>>
>> OK, that's the general idea of sparse matrices. How does it relate to
>> our specific problem?
>
> Just trying to agree with you, i.e., we should keep track of the sparse
> elements of the matrix.
>
But we do. Or, to prevent more confusion, what are "sparse elements"?


-- 
RNDr. Jaroslav Hajek
computing expert
Aeronautical Research and Test Institute (VZLU)
Prague, Czech Republic
url: www.highegg.matfyz.cz