Re: [igraph] arpack implementation in igraph is slow?

[Gábor Csárdi]

Hi,

there are two reasons for this being slow. One is that ARPACK needs a
lot of iterations to converge, around a thousand. The other is that
your callback function itself takes a long time to compute. I measured
and more than 50% of the computation is spent in the callback.

In summary, arpack() is only efficient if you have a large enough
graph, and ARPACK only needs few iterations to converge. You can gain
something with making your callback faster, e.g. writing it in C.

Best,
Gabor

On Sat, Feb 18, 2012 at 4:42 AM, Massimo Franceschet
<address@hidden> wrote:
> Hi.
>
> I am looking for an efficient implementation of the problem of finding the 
> second smallest eigenpair of a large sparse matrix (the Laplacian of an 
> undirected graph). I found the arpack function of igraph and tried it. 
> However, for some reason I cannot get, it is rather inefficient (it is more 
> efficient to compute *all* eigenpairs with eigen function than computing only 
> a few of them). In the following, I give the code I used. Any hint to get a 
> faster implementation is very welcome.
>
> Thanks.
>
> Massimo Franceschet
> http://users.dimi.uniud.it/~massimo.franceschet/
>
>
>
> # This function computes the product of the Laplacian of a graph (represented 
> as a sparse
> # matrix using an adjacency list (adj)) and a vector (x).
> # It takes linear time if the matrix is sparse
> f = function(x, extra=adj) {
>        n = length(adj)
>        v = x
>        for (i in 0:(n-1)) {
>                # neighbors of node i
>                nei = adj[[i+1]]
>                # i-th component of matrix-vector product
>                v[i+1] = x[i+1] * length(nei) - sum(x[nei+1])
>        }
>        v
> }
>
> # This code generates a scale-free graph with 100 nodes and represent it
> # using an adjacency list (I use the neighbors function of igraph)
> g = simplify(barabasi.game(1000, directed=FALSE, m=2))
> n = vcount(g)
> adj = NULL
> for (i in 0:(n-1)) {
>        adj[[i+1]] = neighbors(g, i)
> }
>
> # I compute the two smallest eigenpairs with arpack function (setting ncv=3 
> is even worse)
> tic = proc.time()
> out = arpack(f, options=list(n=n, nev=2, ncv=n, which="SM"), sym=TRUE)
> proc.time() - tic
>
> # It takes this time
>  user  system elapsed
>  11.403   0.044  11.448
>
>
>
> # I compute *all* eigenpairs with eigen fuction
> L = graph.laplacian(g)
> tic = proc.time()
> eig = eigen(L)
> proc.time() - tic
>
> # It takes this time (20 times faster!)
>   user  system elapsed
>  1.135   0.064   0.664
> _______________________________________________
> igraph-help mailing list
> address@hidden
> https://lists.nongnu.org/mailman/listinfo/igraph-help



-- 
Gabor Csardi <address@hidden>     MTA KFKI RMKI