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.

  • $\begingroup$ Have a look at ams.confex.com/ams/pdfpapers/172662.pdf $\endgroup$ Commented Jan 24, 2018 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
    Commented Jan 25, 2018 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$ Commented Jan 25, 2018 at 11:17

1 Answer 1


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.

  • $\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
    Commented Jan 22, 2018 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$ Commented Jan 22, 2018 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
    Commented Jan 23, 2018 at 9:12
  • $\begingroup$ It's not actually my field. I don't know the literature or software, sorry. $\endgroup$ Commented Jan 23, 2018 at 13:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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