<div dir="ltr"><div class="gmail_extra"><div class="gmail_quote">On Wed, Aug 20, 2014 at 4:17 PM, Jed Brown <span dir="ltr"><<a href="mailto:jed@jedbrown.org" target="_blank">jed@jedbrown.org</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div class="">Matthew Knepley <<a href="mailto:knepley@gmail.com">knepley@gmail.com</a>> writes:<br>
>>   In theory, with this one could write very efficient parallel 3d Poisson<br>
>> solvers in PETSc for boxes, which is an important special case that PETSc<br>
>> does not currently support.<br>
><br>
><br>
> Wouldn't you just use MG?<br>
<br>
</div>FFT is O(n log n) and O(n/p (log n) (log p)) parallel complexity while<br>
MG is O(n) and O(n/p log p + log^2 n).  The presence of the (log n)^2<br>
term is one reason some people like to say that MG won't scale, but FFT<br>
or FMM will (Edelman's 1997 paper forecasts that FFT will eventually be<br>
replaced by FMM).<br>
<br>
FMG for a second order discretization is okay with a Cheby/Jacobi 2,1<br>
cycle, so 4 visits to the fine grid and less than 5 work units in total<br>
(you can do slightly better with GS).  If the per-process size is large,<br>
fine-grid memory bandwidth to apply the stencil operations is the<br>
primary cost, followed by a couple more visits of vector work, mostly<br>
because fusing operations is inconvenient.  How does this compare with<br>
the log n term in FFT complexity?<br>
</blockquote></div><br>I was thinking that the 3x would dissolve pretty quickly for the problem sizes</div><div class="gmail_extra">being talked about in the blurb using the analysis above, but I guess we need</div><div class="gmail_extra">
to check.</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>