On Mon, Jan 20, 2014 at 7:26 AM, Jed Brown <[email protected]> wrote:
> "Jose E. Roman" <[email protected]> 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
