CFD Online Discussion Forums

CFD Online Discussion Forums (
-   Main CFD Forum (
-   -   Fast iterative methods (for Laplace equation)? (

pzhang September 25, 2008 18:29

Fast iterative methods (for Laplace equation)?
Does anyone know any iterative method for solving the Laplace equation (with the standard discretization) for which the number of iterations increases linearly with N? (N is the number of mesh points in one coordinate direction, i.e., N = 1/h)

Jacobi, Gauss-Seidel, SOR(unless with the optimal factor) are all O(N^2) method. I wonder if there is an O(N) method.

[multigrid is exceptional as it is O(1): the number of cycles is grid-independent!]

Jed September 26, 2008 05:24

Re: Fast iterative methods (for Laplace equation)?
The stationary iterations you mention require O(K) iterations where K is the condition number. Conjugate gradients requires O(\sqrt(K)). For second order elliptic BVP, K = O(N^2) where N is the number of points in each Cartesian direction. In this sense, unpreconditioned CG satisfies is O(N). But this is still terrible. If the coefficients are smooth enough and the operator is uniformly elliptic, multigrid preconditioning should perform very well. More robust alternatives which also maintain essentially linear cost are multi-level domain decompositions such as BDDC.

By the way, multigrid as a solver rarely beats a Krylov with multigrid preconditioning. Nonlinear multigrid (such as FAS) rarely beats a Newton-Krylov iteration with multigrid preconditioning. Grid sequencing is still useful to get a good initial Newton iterate on the fine mesh.

pzhang September 30, 2008 16:28

Re: Fast iterative methods (for Laplace equation)?

All times are GMT -4. The time now is 16:50.