[petsc-dev] Spectral partitioning

[Matthew Knepley]

On Mon, Jan 20, 2014 at 7:26 AM, Jed Brown <jedbrown at mcs.anl.gov> wrote:

> "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.
>

The spectral part does not use HSL code, but its entirely dense :( I would
be eager for
a SLEPc implementation, but I knew there were caveats.


> > 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.
>

So the same argument that tells you that you have a nice partition, also
tells you
that you have minimized bandwidth, so ordering makes some sense. Also, check
this out: http://arxiv.org/abs/1209.5969. I really want to do this.


> > 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.
>

Will read.

   Matt

-- 
What most experimenters take for granted before they begin their
experiments is infinitely more interesting than any results to which their
experiments lead.
-- Norbert Wiener
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.mcs.anl.gov/pipermail/petsc-dev/attachments/20140120/2e33435d/attachment.html>