[SciPy-User] Matrix-free version of connected_components

[Gael Varoquaux]

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