[SciPy-user] Efficient submatrix of a sparse matrix

William Hunter willemjagter at gmail.com
Fri Sep 8 00:52:14 CDT 2006


It occured to me after I sent the mail that you're probably not into
solving sparse systems, but actually just slicing sparse matrices...
If so, my previous post is obviously not of much meaning to you.

On 07/09/06, Brendan Simons <brendansimons at yahoo.ca> wrote:
> Hi all,
> I have a neat little problem for which I think sparse matrices are
> the answer.   I need to store a bunch of overlapping "intervals", (a,
> b pairs for which any a <= val < b crosses that interval) in a manner
> which makes "stabbing inquiries" (which intervals cross a specified
> value) easy.  The canonical way to to this is with interval trees (a
> good summary here: http://w3.jouy.inra.fr/unites/miaj/public/vigneron/
> cs4235/l5cs4235.pdf), however I think I can simplify things as follows:
> 1)  perform an argsort on the interval a and b endpoints.  This gives
> the position of each interval in an "order" matrix M, where each row
> and each column contains only one interval, and intervals are sorted
> in rows by start point, and in columns by endpoint
> 2) for a "stab" point x, do a binary search to find the row i and
> column j where x could be inserted into M and maintain its ordering.
> The submatrix of M[:i, j:]  would contains all those intervals which
> start before x, and end after x.
> Since the order matrix M is mostly empty it would make sense to use a
> sparse matrix storage scheme, however the only one in scipy.sparse
> that allows 2d slicing is the dok_matrix, and the slicing algorithm
> is O(n), which is much too expensive for my purposes (I have to do
> thousands of stabbing inquiries on a space containing thousands of
> intervals).
> Is there no more efficient algorithm for 2d slicing of a sparse matrix?
>   -Brendan
> --
> Brendan Simons
> __________________________________________________
> Do You Yahoo!?
> Tired of spam?  Yahoo! Mail has the best spam protection around
> http://mail.yahoo.com
> _______________________________________________
> SciPy-user mailing list
> SciPy-user at scipy.org
> http://projects.scipy.org/mailman/listinfo/scipy-user

More information about the SciPy-user mailing list