[SciPy-user] Efficient submatrix of a sparse matrix

[William Hunter]

Brendan;

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

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
>