Computational costs (Electrical Machine)

By

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 astmpF403_thumbwhile 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).

method

2D

3D

dense Cholesky

tmp11-405 tmp11-406

Jacobi

tmp11-407 tmp11-408

Gauss-Seidel

tmp11-409 tmp11-410

band Cholesky

tmp11-411

optimal SOR

tmp11-412 tmp11-413

sparse Cholesky

tmp11-414

conjugate gradient

tmp11-415 tmp11-416

optimal SSOR

tmp11-417 tmp11-418

preconditioned CG

optimal AD I

tmp11-419 tmp11-420

cyclic reduction

tmp11-421 tmp11-422

FFT

tmp11-423 tmp11-424

multigrid V-cycle

tmp11-425 tmp11-426

FACR

tmp11-427 tmp11-428

full multigrid

tmp11-429 tmp11-430

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