[petsc-dev] P3DFFT is an open-source numerical library providing highly scalable implementation of 3D spectral transforms

[Jed Brown]

Matthew Knepley <knepley at gmail.com> writes:
>>   In theory, with this one could write very efficient parallel 3d Poisson
>> solvers in PETSc for boxes, which is an important special case that PETSc
>> does not currently support.
>
>
> Wouldn't you just use MG?

FFT is O(n log n) and O(n/p (log n) (log p)) parallel complexity while
MG is O(n) and O(n/p log p + log^2 n).  The presence of the (log n)^2
term is one reason some people like to say that MG won't scale, but FFT
or FMM will (Edelman's 1997 paper forecasts that FFT will eventually be
replaced by FMM).

FMG for a second order discretization is okay with a Cheby/Jacobi 2,1
cycle, so 4 visits to the fine grid and less than 5 work units in total
(you can do slightly better with GS).  If the per-process size is large,
fine-grid memory bandwidth to apply the stencil operations is the
primary cost, followed by a couple more visits of vector work, mostly
because fusing operations is inconvenient.  How does this compare with
the log n term in FFT complexity?
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 818 bytes
Desc: not available
URL: <http://lists.mcs.anl.gov/pipermail/petsc-dev/attachments/20140820/5d5d8cf7/attachment.sig>