[SciPy-user] sparse SVD

Kenneth Arnold kenneth.arnold@gmail....
Wed May 6 18:52:32 CDT 2009


Stéfan van der Walt:
> Can you tell us a bit more about the sparse tensor representation you use?

We've rolled our own. We first used a dictionary mapping tuples to
keys, but now switched to a nested dictionary format. Those are of
course internal representations; to the user it just looks like
`tensor['dog','IsA','pet']` (which translates into numerical indices
and then into nested dict lookups).

Sidebar:
Currently this wastes some RAM because the dicts aren't specialized to
integer indices (they're just Python objects, which means an extra
pointer at best). This would be a really helpful place to jump in and
contribute, because we're hitting memory limits in our latest
experiments! :) On the other hand, most of our experiments in practice
only use two dimensions, for which we could specialize to use numpy or
cvxopt's sparse matrix implementations.

SVDLIBC uses a compressed-sparse-column representation. We have Cython
code to convert our matrices into that, after unfolding tensors to
matrices if necessary.

And by the way: we use numpy's ndarray for dense tensor storage, but
we need iteration to be dict-like (i.e., over tuples of keys), so we
have to wrap ndarray. This works, but is tedious and slows things
down. Any better ideas?

About licensing: after some internal discussion, we concluded that
staying GPL overall is necessary. We may be able to relicense some of
the lower-level stuff (like the sparse tensor code), depending on
interest.

-Ken



2009/5/1 Stéfan van der Walt <stefan@sun.ac.za>:
> Hi Ken
>
> 2009/5/1 Kenneth Arnold <kcarnold@mit.edu>:
>> We think that significant chunks of this code would make a great
>> addition to numpy/scipy. We don't have the resources to push
>> integration ourselves, though, but we could certainly help anyone who
>> is interested in assimilating our code. And in the mean time it should
>> be useful to anyone wanting to run sparse SVDs.
>
> We are always glad for new code contributions!  SciPy and NumPy are
> BSD licensed, so would your lab be able to relicense the code?  I
> think we could benefit from having both SVDLIBC and ARPACK sparse SVD
> wrappers in SciPy.
>
> Can you tell us a bit more about the sparse tensor representation you use?
>
> Regards
> Stéfan
> _______________________________________________
> SciPy-user mailing list
> SciPy-user@scipy.org
> http://mail.scipy.org/mailman/listinfo/scipy-user
>


More information about the SciPy-user mailing list