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!]

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.

Thanks!