Re: [Pysparse-users] Full matrix conversion to spmatrix.ll_mat

[Dominique O. <dom...@gm...>]

On Wed, Nov 18, 2009 at 11:47 AM, iza...@t-...
<iza...@t-...> wrote:
> Dear Sirs,
>
> Im using pysparse with the eigenvalue solver jdsym. It works great !!.  The
> only problem I have at the moment is the conversion time from the original
> format of my matrix. Here is a description of my process:
>
> - Read a file wit around 20000 points
> - Process this points and get a very big array (20000*20000) (this part is
> done with pyrex)
> - I reshape the array into a matrix (20000,20000)
> - I do some math ( matrix transpose, matrix scaling, dot product, transpose,
> etc.)
> - I get a matrix from which I would like to obtain a couple of eigenvectors
>
> In order to use jdsm I need the matrix in linked list format. I have tried
> several things:
>
> - write the matrix in matrix market format (using scipy) and the read with
> spmatrix.ll_mat_from_mtx
>   (it takes very very long)
> - convert directly to sparse coo format and then into  ll format
>  (I get an error that this format is not supported for conversion)
> - use the internal routine put(V,index1,index2)
> (this is faster but still takes a long time compared with the eigenvalue
> problem)
>  - I also use
>    for ii in range(N):
>     for jj in range(N):
>         Al[ii,jj]=K[ii,jj]
> (this is almost the same as using put)
>
>
> Is there any way to have it faster in the right format? This will improve a
> lot the all process of obtaining the eigenvalues. If would be great  to have
> something like:
>
> spmatrix.ll_mat(K)
>
> where K is a full matrix.
>
> I appreciate any help with this problem.

Hi Rodrigo,

Thanks for using PySparse! All comments can help us improve the
library. A (rough) design decision in PySparse is that matrix
operations should be "cheap", i.e., O(nnz), for matrices that are
indeed sparse. If your matrix is dense, I'm afraid any constructor of
the form spmatrix.ll_mat(K) will require O(n^2) operations. Please
correct me if I'm wrong but the Matrix Market format lists all the
nonzero elements of your matrix, and we *do* need all that information
to construct the matrix. I don't see how to lower this cost. Using a
different sparse format won't help either.

What could help is detect any exploitable structure in your matrix.
Yes it is dense but it probably isn't random and may have some pattern
to it. For instance, it could be (anti-)symmetric, (block-)circulant,
(block-)Toeplitz, or whatever. I feel that is where savings might be
found.

Alternatively, is there any chance to bypass the 2-dimensional array
that you process before building the PySparse matrix, construct the
PySparse matrix directly and operate on it instead? Or operate on
arrays of the form (irow,jcol,val) and then use put()?

I hope this helps. Good luck.

-- 
Dominique