|
|
Ublas : |
From: Paul C. Leopardi (leopardi_at_[hidden])
Date: 2005-08-14 05:08:15
Hi Michael,
My responses below,
Best regards
On Sat, 13 Aug 2005 03:05 am, Michael Stevens wrote:
> Paul,
>
> On Tuesday 02 August 2005 02:45, Paul C. Leopardi wrote:
>
> Any ideas how such a change could be done. I can't see a way to convince
> the compiler that the temporary is initialised.
Most likely, don't use the temporary at all?
> Since you are using sparse_prod I have a question. Any idea what it is
> supposed to do.
AFAIK, it is supposed to multiply sparse matrices more quickly than the usual
multiply, with the time for sparse LHS*RHS being O( nnz(LHS)*size(RHS,2) )
(in Matlab notation), versus something like
O( size(LHS,1)*size(LHS,2)*size(RHS,2) ) for the usual multiply.
> The code is littered with issues and possible bug. For
> example the dense 'temporary' seems very odd for a "sparse" function.
I did not write this code, but here is my guess.
The variable 'temporary' is similar to a matlab sparse accumulator [Gilbert92
3.1.3 pp. 9-10.]. It may need to be dense because it is used to store each
row of the result LHS*RHS. There may be no easy way to predict the union of
the sparsity patterns of each of the rows of LHS*RHS, but it must be a subset
of the union of the sparsity patterns of the rows of RHS.
Matlab uses a similar approach, but uses columns rather than rows, with the
union of the sparsity patterns of the columns of LHS*RHS being a subset of
the union of the sparsity patterns of the columns of LHS.
The other way in which Matlab differs from sparse_prod is that Matlab uses an
unsorted vector of indices of nonzero entries of the sparse accumulator, to
avoid having to iterate over all entries of the sparse accumulator when
constructing each sparse column of LHS*RHS. Perhaps sparse_prod could be
modified to do the analogous thing for rows?
References:
[Gilbert92]
Gilbert, John R., Cleve Moler, and Robert Schreiber, "Sparse Matrices in
MATLAB: Design and Implementation," SIAM J. Matrix Anal. Appl., Vol. 13, No.
1, January 1992, pp. 333-356.
http://www.mathworks.com/access/helpdesk/help/pdf_doc/otherdocs/simax.pdf
http://www.nada.kth.se/kurser/kth/2D1252/gilbert92sparse.ps
[Walder]
Walder, Christian, "Sparse Matrix Multiplication",
http://www.mathworks.com/matlabcentral/fileexchange/loadFile.do?objectId=7466&objectType=file