[SciPy-User] Matrix-free version of connected_components

Per Nielsen evilper@gmail....
Thu Aug 2 02:07:27 CDT 2012


Thanks for the reply.

This approach looks like it could do the job, although it appaers to be
significantly more computationally demanding than connected_components, due
to the repeated need to find the Fiedler vector of very large systems. But
I will give it a go! :)

Per

On Wed, Aug 1, 2012 at 3:18 PM, Gael Varoquaux <
gael.varoquaux@normalesup.org> wrote:

> You can try spectral graph partioning, computing the Fiedler with arpack,
> that only needs matrix-vector product:
> http://mathworld.wolfram.com/FiedlerVector.html
> http://en.wikipedia.org/wiki/Algebraic_connectivity
>
> HTH,
>
> Gael
>
> On Wed, Aug 01, 2012 at 02:15:51PM +0200, Per Nielsen wrote:
> > Hi all,
>
> > I work with large sparse matrices which consists of several disconnected
> > components and I only need one of these. So far I have succesfully been
> > using scipy.sparse.csgraph.connected_components to dig out the component
> I
> > needed. This algorithm does however require the entire sparse matrix as
> > input, which sometimes is too large to fit in memory.
>
> > For this reason I wondered whether there existed a matrix-free version
> > of connected_components, or another algorithm achieving the same, where I
> > would only need to provide a function calculating the sparse
> matrix-vector
> > product.
>
> > Any help, hints, or information would be greatly appreciated :)
>
> > Cheers,
> > Per
>
>
> --
>     Gael Varoquaux
>     Researcher, INRIA Parietal
>     Laboratoire de Neuro-Imagerie Assistee par Ordinateur
>     NeuroSpin/CEA Saclay , Bat 145, 91191 Gif-sur-Yvette France
>     Phone:  ++ 33-1-69-08-79-68
>     http://gael-varoquaux.info            http://twitter.com/GaelVaroquaux
> _______________________________________________
> SciPy-User mailing list
> SciPy-User@scipy.org
> http://mail.scipy.org/mailman/listinfo/scipy-user
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mail.scipy.org/pipermail/scipy-user/attachments/20120802/f9d4f9f9/attachment-0001.html 


More information about the SciPy-User mailing list