<div dir="ltr"><div class="gmail_extra"><div class="gmail_quote">On Mon, Jan 20, 2014 at 7:26 AM, Jed Brown <span dir="ltr"><<a href="mailto:jedbrown@mcs.anl.gov" target="_blank">jedbrown@mcs.anl.gov</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">"Jose E. Roman" <<a href="mailto:jroman@dsic.upv.es">jroman@dsic.upv.es</a>> writes:<br>

<br>
> Hi Jed,<br>
><br>
> I saw you added spectral partitioning<br>
> <a href="https://bitbucket.org/petsc/petsc/commits/fc1bef75356" target="_blank">https://bitbucket.org/petsc/petsc/commits/fc1bef75356</a><br>
<br>
This was entirely based on Matt's code, which included some HSL code<br>
that we don't have a license to include.  I refactored to avoid that.<br></blockquote><div><br></div><div>The spectral part does not use HSL code, but its entirely dense :( I would be eager for</div><div>a SLEPc implementation, but I knew there were caveats.</div>
<div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">
> One thing I do not understand is why is it in MatOrdering. Shouldn't<br>
> it be in MatPartitioning? My understanding was that MatOrdering was<br>
> intended for fill-reducing orderings for PCFactor.<br></blockquote><div><br></div><div>So the same argument that tells you that you have a nice partition, also tells you</div><div>that you have minimized bandwidth, so ordering makes some sense. Also, check</div>
<div>this out: <a href="http://arxiv.org/abs/1209.5969">http://arxiv.org/abs/1209.5969</a>. I really want to do this.</div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">

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

><br>
> On the other hand, this recent paper formulates the problem differently and uses LOBPCG to solve a generalized eigenproblem:<br>
><br>
> [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.<br>
> <a href="http://epubs.siam.org/doi/abs/10.1137/120898760" target="_blank">http://epubs.siam.org/doi/abs/10.1137/120898760</a><br>
<br>
Interesting.<br>
</blockquote></div><br>Will read.</div><div class="gmail_extra"><br></div><div class="gmail_extra">   Matt<br clear="all"><div><br></div>-- <br>What most experimenters take for granted before they begin their experiments is infinitely more interesting than any results to which their experiments lead.<br>
-- Norbert Wiener
</div></div>