Will a multi-grid method damp out the high frequency physical wave?
 

I am solving time-dependent problem, which contains physical waves with different frequencies. The NS equations I use contain a Poisson's equation. I use iterative method to solve it, but I find the convergence speed is very low.

Hence, I hope to use a multi-grid method to accelerate the convergence. However, I am afraid that the high frequency physical waves cannot be represented in a coarse grid and my simulation target will be damped out.
Will this happen?

By the way, I feel rather confused about the concept of "low frequency errors" in multi-grid method. Is it the same thing as the physical waves with low frequency I need to simulate?

Thank you in advance.

What method?

Quote:

Hence, I hope to use a multi-grid method to accelerate the convergence.

Works really well for linear problems, tend to need multiple cycles for nonlinear ones.


No. The coarser grids are just used to get an error estimate that is then "prolonged" back to the fine grids. In the end you still have a solution on your fine grid that includes the higher resolution information.


Not really; lots of iterative methods (eg. point Gauss-Seidel, SSOR) are good at getting rid of high frequency error, but take many iterations to smooth out the low-frequencies. By going to a coarse grid, what used to be low frequency errors on the fine grid become higher frequency (which the method handles well), so convergence speeds up.

Quote:

Thank you in advance.

HtH,
Josh

Hi,
I have encountered the same problems as you.
Do you mean that your MG doesn't work well?
I have experiences that at first I checked up MG's procedure by programming 1D problem and then challenged 3D one which was my aim.

http://www.geocities.jp/viola08129/

Thank you all very much.
I have programmed the multi-grid method. However, I really find the wave amplitude is 10% smaller by multi-grid method than only using a fine grid.
Is this a normal result of multi-grid method?
By the way, when solving the Poisson’s equation, I didn’t use the restriction operatior on the source term. Is it necessary?
Thank you.

restriction operatior etc.
 

Hi,hadesmajesty


[QUOTE=hadesmajesty;230777]Thank you all very much.
I have programmed the multi-grid method. However, I really find the wave amplitude is 90% smaller by multi-grid method than only using a fine grid.
Is this a normal result of multi-grid method?

It isn't a normal result, I think.:confused:

By the way, when solving the Poisson’s equation, I didn’t use the restriction operatior on the source term. Is it necessary?

Necessary for rsiduals(source term?).

V cycle procedure I used with max. grid level 3 for linear equation system(1D problem) Aw=G is as follows;

w=0 ! initial solutions
f[3]=G ! initial residuals at max. grid level=3
do i=1,niter ! n in [n]:grid level
f[2]=R[2,3]*f[3]
f[1]=R[1,2]*f[2]

u[3]=0 ! initial residual at g.l.=3
u[3]=relax(A[3]*u[3]=f[3]) ! relaxation for residual eq. at g.l.=3
f[2]=R[2,3]*(f[3]-A[3]*u[3]) ! restriction for residuals f

u[2]=0
u[2]=relax(A[2]*u[2]=f[2])
f[1]=R[1,2]*(f[2]-A[2]*u[2])

u[1]=inv(A[1])*f[1] ! exact solution at g.l.=1

u[2]=u[2]+I[2,1]*u[1] ! prolongation and correction
u[3]=u[3]+I[3,2]*u[2]

f[3]=f[3]-A[3]*u[3]
w=w+u[3] ! correction for solution

end do

Thank you.

Do you run a sweep (or a couple) of your solver one last time on the fine grid to kill off the high-frequency errors? You should be converging to the same solution, multigrid just gets you there with less work (hopefully).

Thank you very much, jstults and trout. I think I have found what’s wrong.
To solve Ax=b.
Last time I used the iteration scheme like, x(n)=G*x(n-1)+b, where G and b are fixed in all iterations, and just transferred the unknown x and the source term b between the coarse and fine grids.

Now I used the iteration scheme: Residual=(A*x(n-1)-b)
dx=G’* Residual
x(n)= x(n-1)+dx
I transfer the residual (A*x(n-1)-b) between the two grids. The multi-grid cycle is that: first sweep two times on the fine grid, then transfer and sweep one time on the coarse grid, and then go back to fine grid. This time I find the result is the same as just using fine grid.

However, the above algorithm has larger computational cost, because I have to do matrix multiplication for two times : first A*x(n-1) for the residual and second G’* Residual for dx. Therefore, the final computational times are as below:
1. directly solve x only on fine grid: 4.46s.(my old method)
2. Solve residual and then dx only on fine grid: 6.73s.
3. Solve residual and then dx by multi-grid: 4.61.
So, compare the time used by 1. and 3. The multi-grid method cannot improve anything. Is my current algorithm correct? Or is there any place to improve?

Thanks again.

Check out this site, especially slides 59 and 60 of the slides. It lays out an algorithm for a straightforward two-level coarse grid correction scheme, which seems like what you are trying to do.

The early slides are also good, they talk to your original questions about the low/high frequency errors.

Thanks a lot.
I follow the book of William Briggs and use a two-level coarse grid correction method. The solution is correct, but the convergence speed has not been improved or even lower.

The Poisson's equation I solve is a*d^2u/dx^2+d^2u/dy^2=f, in which 0<a<<1. Hence, I use Gauss-Seidel line iteration by solving variables in y direction at the same time. In the coarse grid correction step, according the book of William Briggs, I just coarsen the grid in y direction. For each line, I calculate the residual, then the error and update the new value. After that I go to next line and repeat the above procedure again.

I am not sure how to implement the coarse grid correction method with the Gauss-Seidel line iteration. Is my algorithm correct?

Thank you very much.