[SciPy-User] Matrix-free version of connected_components

[Daπid]

I am not sure if this is what you are looking for, but an alternative
approach would be to transform the matrix into a graph, and then get
the connected components using, for eample, networkx. You can find a
complete description about the topic in: "Complex networks: Structure
and dynamics" S. Boccaletti et al. (2006) Phys. Reports. Sorry that I
cannot provide anything more concise.


David.

On Thu, Aug 2, 2012 at 8:07 AM, Per Nielsen <evilper at gmail.com> wrote:
> 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 at 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 at scipy.org
>> http://mail.scipy.org/mailman/listinfo/scipy-user
>
>
>
> _______________________________________________
> SciPy-User mailing list
> SciPy-User at scipy.org
> http://mail.scipy.org/mailman/listinfo/scipy-user
>