[petsc-dev] Spectral partitioning

[Jed Brown]

"Jose E. Roman" <jroman at dsic.upv.es> writes:

> Hi Jed,
>
> I saw you added spectral partitioning
> https://bitbucket.org/petsc/petsc/commits/fc1bef75356

This was entirely based on Matt's code, which included some HSL code
that we don't have a license to include.  I refactored to avoid that.

> One thing I do not understand is why is it in MatOrdering. Shouldn't
> it be in MatPartitioning? My understanding was that MatOrdering was
> intended for fill-reducing orderings for PCFactor.
>
> I always wanted to do spectral partitioning with SLEPc. I started years ago with a Matlab script that makes spectral bisection recursively for log2(np) levels, using a generic eigensolver (eigs) in each level. It works well, but it is necessary to add a refinement step between each level (Fiduccia-Mattheyses). That is one of the reasons why I did not even start the implementation in SLEPc.
>
> On the other hand, this recent paper formulates the problem differently and uses LOBPCG to solve a generalized eigenproblem:
>
> [1] E. Vecharynski, Y. Saad, and M. Sosonkina. Graph partitioning using matrix values for preconditioning symmetric positive definite systems. SIAM Journal on Scientific Computing, 36(1):A63–A87, 2014.
> http://epubs.siam.org/doi/abs/10.1137/120898760

Interesting.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 835 bytes
Desc: not available
URL: <http://lists.mcs.anl.gov/pipermail/petsc-dev/attachments/20140120/1da8c725/attachment.sig>