Preconditioning Revisited 461 Idea

We have now introduced the classical iterations, the multigrid method, domain decomposition and the Conjugate Gradient method as separate methods. It is now time to combine them to derive a framework suitable for handling the equations of the Bidomain model. The gluing concept is preconditioning. As before, we want to solve the linear system

We saw earlier that the efficiency of both the Richardson and the Conjugate Gradient method depends on the condition number of A, which was typically of order h-2. The idea of preconditioning is simply to multiply (4.105) with a matrix or linear operator B to obtain an equivalent system, where B is usually called thepreconditioner. The system (4.106) has the same solution as (4.105) provided that B has full rank6. The hope is then that (4.106) is easier to solve than (4.105). The preconditioner B can be any matrix or linear operator that in some sense resembles A-1 .For instance, it may be based on an approximate factorization of A, or it may be a sweep with the Jacobi or the multigrid method. What is crucial is that B should be a good approximation of A-1 and also inexpensive with respect to storage and evaluation.

Earlier, we considered order-optimal solution algorithms, and we will now relate these algorithms to order-optimal preconditioners. First, we need the concept of spectral equivalence, which describes what a "good" approximation of A-1 is.

4.6.2 Spectral Equivalence

Notice that A and B are families of matrices with respect to the triangulations Qh of Q, where h approaches zero in the limit. It is, therefore, common to let A and B have the subscript h, Ah and Bh.

The two linear operators or matrices, A-1 and Bh, which are assumed to be symmetric and positive definite7, are spectrally equivalent (independent of h) if there exist constants c1 and c2, independent of h such that

Alternatively, we may express this property as

C1(Ahv,v) < (AhBhAhv,v) < C2(Ahv,v), Vv. (4.108)

6 A matrix has full rank if it is invertible.

7 If Ah and Bh are symmetric and positive definite then so are A- and B- .

It is known that if A-1 and Bh are spectrally equivalent, the condition number of BhAh is bounded by the constants c1 and c2,

It is common to denote spectral equivalence of A-1 and Bh by A-1 ~ Bh.

With the definition of spectral equivalence we can now state what a well-designed preconditioner should look like:

- Bh should be spectrally equivalent to A-1,

- the evaluation of Bh on a vector v, Bhv, should cost O(N) operations,

- the storage of Bh should be similar to the storage of Ah, O(N) floating point numbers.

In what follows we will see that an order-optimal preconditioner leads to an order-optimal solution algorithm, in the case of both the Richardson and the Conjugate Gradient methods.

4.6.3 The Richardson Iteration Re-Revisited

We can now derive what the spectral equivalence of B and A-1 means in the context of the preconditioned Richardson iteration. We remember from (4.28) that the error at the n iteration, en, could be stated in terms of the error at the previous iteration, en-1:

The convergence rate in the A-norm is

and the error reduction can be estimated as

Because BA is symmetric with respect to the A inner product, pA can be stated in terms of the eigenvalues of BA, ¡i,

Hence, pA is a linear polynomial in pi and its maximum is obtained at the extreme values of ¡i,

\1 - Tpo\ or |1 - TpN|, where ¡0 and ¡N are the smallest and largest eigenvalues, respectively. We choose t as the minimizer of \ 1 - Tpi\. The minimum is obtained when

which makes

the optimal choice. With this choice of t, pA is

1 1 2Io in - Io K -1 PA = 1 - Tlo = 1----=---= „ , ,, , (4.112)

and we have the corresponding error estimate,

0 0

Post a comment