By R. Belmans
Table 8.1 summarises the computational cost of solving an elliptic boundary value problem on a mesh of size kxk (2D) or kxkxk (3D). The formulas are valid for the Poisson equation on the unit square, discretised with second order central differences. For more complicated PDEs, domains, boundary conditions or discretisation schemes some of the methods may not be viable options (e.g. FFT based techniques).
The complexity of a method is often written as a function of n, where n is the order of the coefficient matrix. Table 8.2 states the exponents of n in the computational cost of solving a 2D or 3Delliptic problem. Note that the cost of a dense direct solver increases aswhile multigrid solves a problem at a cost proportional to n.
Table 8.1. Computational complexity of direct and iterative methods for the solution of the problem on a rectangular mesh with k mesh-points in every direction (Heath p.344).
Table 8.2. Exponent of n (total number of mesh-points) in the computational complexity of direct and iterative methods applied to the model problem Poisson equation (Heath , p.345).
method |
2D |
3D |
dense Cholesky |
3 |
3 |
band Cholesky |
2 |
2.33 |
sparse Cholesky |
1.5 |
2 |
conjugate gradient |
1.5 |
2 |
preconditioned CG |
1.25 |
1.17 |
full multigrid |
1 |
1 |