1
$\begingroup$

I have a 3D solver for the incompressible Navier-Stokes equations which uses a FFT library for the Poisson equation with a uniform grid on all directions. In 2D the Poisson equation is given by:

$$ p_{xx} + p_{yy} = f_{rhs} $$

When using a non-uniform grid, we usually map the domain to a computational space where the grid is uniform. Let $x = x(\xi), y = y(\eta)$. The Poisson equation on the computational grid is:

$$ p_{\xi \xi} \, \xi_{x}^2 + p_{\eta \eta} \, \eta_{y}^2 + p_{\xi}\, \xi_{xx} + p_{\eta} \, \eta_{yy} = f_{rhs} $$

Although I do have a background in numerical methods, my knowledge of FFT methods is limited. Is the Poisson equation on a non-uniform grid solvable with FFT methods? If not, what are the alternatives? Note that for reasons that take some time to explain, multigrid and classic iterative methods (e.g. jacobi...) are not an option. Or rather they were shown unstable for certain applications.

$\endgroup$
  • $\begingroup$ Have a look at ams.confex.com/ams/pdfpapers/172662.pdf $\endgroup$ – Vladimir F Jan 24 '18 at 16:37
  • $\begingroup$ @VladimirF Thanks for the read! I had thought of doing some kind of iterative process. I see from your github you have written your own FFT Poisson solver for uniform grids. Do you have any experience with non-uniform grids? I'm just getting familiar with he literature but do you see any problem with solving the first equation directly using NUFFT (type I) for Neumann-Neumann or Periodic-Periodic BC? $\endgroup$ – user26633 Jan 25 '18 at 10:12
  • $\begingroup$ I think it should work, but I don't have any experience nor do I have an idea how fast will it be. $\endgroup$ – Vladimir F Jan 25 '18 at 11:17
2
$\begingroup$

First, there are non-uniform mesh FFT variations that you could use without having to do the coordinate transformation.

Second, the FFT is not easily applicable to the transformed problem. The reason why the FFT is easily applicable to the Laplace equation without transformation is that (showing this for the 1d case here) $$ {\cal F}[p_{xx}](k) = -k^2 {\cal F}[p](k), $$ i.e., the derivative simply yields a factor under transformation. Consequently, the equation $-p_{xx}=f$ gives you $$ k^2 {\cal F}[p](k) = {\cal F}[f](k), $$ and thus $$ {\cal F}[p](k) = \frac{1}{k^2}{\cal F}[f](k), $$ which is easily invertible to $$ p(x) = {\cal F}^{-1}\left[\frac{1}{k^2}{\cal F}[f](k)\right](x). $$ But if, on the left hand side, you start with $g(\xi)p_{\xi\xi}(\xi)$, then things are not that simple because $$ {\cal F}[g(\xi)p_{\xi\xi}(\xi)] \neq k^2 {\cal F}[g](k){\cal F}[p](k) $$ or anything similarly simple that would allow you to isolate ${\cal F}[p](k)$ to one side.

$\endgroup$
  • $\begingroup$ Thank you for your answer! What about applying the FFT to a non-equidistant grid? Would it lead to the same conclusion? $\endgroup$ – user26633 Jan 22 '18 at 20:14
  • $\begingroup$ No -- you're still doing a Fourier transform (which is what you need for the properties in question), you just happen to do so on a non-uniform grid. So, using a non-uniform FFT will allow you to solve the PDE without problem. $\endgroup$ – Wolfgang Bangerth Jan 22 '18 at 21:39
  • $\begingroup$ So using a non-uniform FFT on the original equation ($p_{xx}+p_{yy} = f_{rhs}$) will make the equation in the frequency space separable? That works for me as well. It just needs to handle Neumann and Periodic BC. My objective is to solve the PDE, how I do it is not important. I've been looking looking for a non-uniform FFT solver for the Poisson equation but have not found any. I think I'll have to implement it myself. Would you recommend any particular book or tutorial on the subject? $\endgroup$ – user26633 Jan 23 '18 at 9:12
  • $\begingroup$ It's not actually my field. I don't know the literature or software, sorry. $\endgroup$ – Wolfgang Bangerth Jan 23 '18 at 13:19

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.