[petsc-users] Slepc - SVD routines

[Jose E. Roman]

On 07/07/2010, Luke Bloy wrote:

> Hi,
> 
> First off I apologize for the slepc question, they don't have a users lists so I'm hoping someone on here might be able to offer some guidance.
> 
> Problem:
> I'm working on a graph partitioning problem. Basically I have the laplacian of a large graph and am interested in extracting its connected sub components. An approach is to compute the smallest eigenvalues and eigenvectors of the laplacian matrix. it is known that the lowest eigenvalue of the laplacian is 0, and has a multiplicity of K if the graph has K subcomponents. These subcomponents can be extracted from the smallest eigenvectors.
> 
> Question:
> What is the best approach within slepc to attack this problem?
> 
> I've been using SVD solvers using the LANCOS method to attack this problem, but sometimes have convergence problems. I know one of the smallest eigen vectors is the vector of all ones, and have tried to initialize the svd solver with this vector but this has led to very strange problems.
> 
> Would I be better off using one of the EPS solvers? If so which can correctly extract multiplicities of eigenvalues?
> 
> Thanks,
> Luke

SLEPc's example 11 (http://www.grycap.upv.es/slepc/documentation/current/src/examples/ex11.c.html ) computes the Fiedler vector of a graph, i.e., the second eigenvector of the Laplacian (assuming a connected graph).

The example uses EPS because for symmetric (semi-)definite matrices the singular value decomposition is equal to the eigendecomposition.

In your case, you want to explicitly compute the eigenspace associated to the zero eigenvalue. Then you can simply use ex1.c choosing the smallest eigenvalues (e.g. with the flag -eps_smallest_real). The default EPS solver (Krylov-Schur) shouldn't have any problems with multiple zero eigenvalues.

If you can't get it work, contact us at the slepc-maint email address.

Regards,
Jose