FFT Poisson Solver for non-uniform grid

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.

• Have a look at ams.confex.com/ams/pdfpapers/172662.pdf – Vladimir F Jan 24 '18 at 16:37
• @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? – user26633 Jan 25 '18 at 10:12
• I think it should work, but I don't have any experience nor do I have an idea how fast will it be. – Vladimir F Jan 25 '18 at 11:17

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.
• 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? – user26633 Jan 23 '18 at 9:12