Multigrid Methods Sample Clauses

Multigrid Methods. We start by introducing multigrid methods, which are often used as a preconditioning technique that will be of high importance in this thesis. We follow [20] for explaining the concept of multigrid. We start with considering a general linear system of the form Ax = f. (6.1) For now we want to assume that the matrix A is obtained by discretizing a partial differential equation on a given domain, i.e. the matrix A is associated to a mesh. When it is not feasible to compute the exact solution x to (6.1), some approximation x˜ is found. The corresponding (unknown) error is given by e = x − x˜. We may compute the residual r = Ax˜ − f. The residual equation Ae = r (6.2) can be easily derived from the considerations above. Suppose now that an approxi- mation x˜ to (6.1) has been computed. The approximation can be improved by solving (6.2) for e and then updating x by x = x˜ + e. (6.3) . ΣΣ Σ One way to find an approximate solution to (6.1) is by applying a fixed number of iterations of a stationary iterative method (see Appendix A). When testing stationary iterative methods on cases where the analytical solution (hence the error at each iteration is known), it can be observed that the norm of the error drops quickly for the first few iterations, but reduces slowly for the proceeding iterations. This is due to the fact that stationary iterative methods tend to “smooth” out the high frequency modes of the error, whereas the low frequency modes are damped significantly slower. More precisely, if we assume that the error corresponding to the initial guess has the form e = {ei}n n i=1 = k=1 αk . sin kiπ n n i=1 , αk ∈ R, then those components of the error corresponding to large values of k (i.e. the high frequency modes) are are damped rapidly while those components corresponding to the lower values of k (the low frequency modes) decrease much more slowly. Whether a frequency mode is to be considered high or low depends on the size of the mesh h = 1/n. The property of eliminating high frequency modes and leaving low frequency modes is called the smoothing property. The idea behind multigrid is to first apply a fixed number of an iterative scheme