Re: About diagonal matrices

[Daniel J Sebald]

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.


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


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

Dan