[Scipy-tickets] [SciPy] #1057: sparse matrix graph algorithms
SciPy Trac
scipy-tickets@scipy....
Sun Jul 4 02:15:30 CDT 2010
#1057: sparse matrix graph algorithms
--------------------------+-------------------------------------------------
Reporter: rc | Owner: wnbell
Type: enhancement | Status: needs_review
Priority: normal | Milestone: Unscheduled
Component: scipy.sparse | Version: devel
Keywords: |
--------------------------+-------------------------------------------------
Comment(by stefan):
Replying to [comment:8 rc]:
> Stefan, do you have reference for that O(n) algorithm?
>
> The code is based on a function that was laying on my disk for quite a
time, so I am not sure about its order. A quick look suggests that it is
proportional to the number of nonzeros, which is in my field (finite
element simulations) O(n), but can be with a non-negligible constant. So
maybe we can do better, if the algorithm can be adapted to CSR kind of
storage. Anyway it is quick enough for me (493039x493039 with 12977875
nonzeros in 0.2 s) :-} (bad argument, yeah).
Sure, I can do one better! Here is some code with references in the
docstring:
http://dip.sun.ac.za/~stefan/code/lulu.git/?p=stefan/lulu.git;a=blob;f=lulu/ccomp.pyx;h=6bbb73bc22f0865a09e4808d121baaacc3d81404;hb=HEAD
--
Ticket URL: <http://projects.scipy.org/scipy/ticket/1057#comment:9>
SciPy <http://www.scipy.org>
SciPy is open-source software for mathematics, science, and engineering.
More information about the Scipy-tickets
mailing list