[SciPy-user] Efficient submatrix of a sparse matrix

William Hunter willemjagter at gmail.com
Thu Sep 7 10:10:58 CDT 2006

You might consider making use of UMFPACK (.../scipy/linsolve/umfpack)?
I'm still figuring it out myself, so this is all I can offer :( I
think it will require you to do some of your work in C.

See http://www.cise.ufl.edu/research/sparse in order to download the
sources (and more). The instructions on the website are very clear and
well written.

Hope this helps (a bit?)

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