Hi everybody, I'm searching for the best (rapid) method to resolve a 3D Poisson's equation (in space) with stretched grid for 2 directions (the last one is uniform). I precise that's it should be applicable to a finite difference resolution. For the moment, I'm thinking about the Multigrid Method or Non Uniform FFT... Thanks

I am a fan of multigrid. There are some more interesting points of it, e.g. whole SIMPLE as a smoother on ALL grid levels (idea by Milovan Peric), and the strategy of the "Nested Iteration". I am sure multigrid is more efficient than FFT. In "Numerical Recipes" you can find the linear and the FAS one as subroutines for finite difference discr. , but the FAS isn't really needed. I can give you some papers for multigrid if you want it, but only in german language.

Is there such a thing as a nonuniform FAST Fourier transform? I would like to know more about that. Any good references?

Could any of you please suggest me a reference from where I can get to know about implementation of FFT to solve a PDE like Poission's equation. I am also facing the same problem of slow convergence rate and dont want to implement the multigrid method because it's a little complex

Here's a package that might be useful (http://www.fftw.org). They have both serial and parallel versions.

For finite difference here are 2 packages i know of http://www.scd.ucar.edu/css/software/fishpack/ http://www.scd.ucar.edu/css/software/mudpack/

Thanks everybody

Hubert> Thanks for your help but I dont speak a word of german.

Mani> For Non Uniform FFT, I suggest you "Fast Fourier transforms for nonequispaced data:A tutorial" D.Potts, G.Steidl, M.Tasche. You can also find some C routine of the method on the Web (don't remember where).

shekharc> Standard FFT => Numerical recipes

Agg> Thank you. I will look this soon.

Hubert> For the Poisson's equation, I don't need the FAS for nonlinear elliptic operator because Laplacian is linear. Isn't it ?

Sorry, another question: Is Numerical Recipes method for Multigrid easily converted to 3D and non uniform grid in 2 ( on 3) directions ?

Fourier and cyclic reduction approaches are usually 'best' whenever they are applicable.

A multigrid approach is usually the 'best' general approach. Here is a web site full of multigrid algorithms and code:

http://www.mgnet.org/

Yes that's right. In certan circumstances you nead FAS if you want to solve a nonlinearity in the iteration step, e.g. heat conduction as a function of temperature itself. or in compressible flows (especially high speed gas flows). The density as a function of temperature, this introduces strong nonlinearities into the solution, causing divergence. The root of this problem is solving the total enthalpy or rothalpy (in general codes), which causes errors in velocities and turbulent kinetic energy, which leads to erros in temperatur.

Yes it is very easy to converted it into 3d, because it's just only the quit normal Poison equation without SIMPLE or turbulence or Navier-Stokes are any thing else we found in CFD normaly. It is only a short subroutine (for both linear and FAS).

There is at least one very important thing to keep in mind: I don't really know much about FFT and its behauviour for convergence, but every algorithm i know for solving the diagonal matrix has problems with very large meshes. First of all the simple Gaus Seidel relaxation. So when you want to do aero dynamics you need very large grids, and at a special border of mesh size (depended to the solver algorithm) the cells react only of the changing of there neighbour cells, and don't progress in convergence. Never the less you will see a flat line for the residuals. That's a great problem especially with large tet meshes, because the neihgbour coupling consists only of 4 cells instead of 6 in hex meshes. Multigrid converges linear, means the mesh size is (almost) independed to the convergence behaviour. I think in 10 years we will have so powerfull computers that we want bigger and bigger meshes, and we all will use multigrid as a must.

shekharc, what you are looking for is called "spectral method" (more general but including FFT). There is a comprehensive Annual Review in Fluid Mechanics by Hussaini and Zang (1987)... old but still valid.

The principle is simple though, it's basically the same thing you did in your undergraduate analysis class: use the Fourier transform to solve a linear PDE analytically. Only in this case you do it numerically for nonlinear problems.