The goal of this chapter is to develop efficient solvers for the discrete linear systems resulting from discretization of the Fredholm integral equation of the second kind by using the multiscale methods discussed in previous chapters. We introduce the multilevel augmentation method (MAM) and the multilevel iteration method (MIM) for solving operator equations based on multilevel decompositions of the approximate subspaces. Reflecting the direct sum decompositions of the subspaces, the coefficient matrix of the linear system has a special structure. Specifically, the matrix corresponding to a finer level of approximate spaces is obtained by augmenting the matrix corresponding to a coarser level with submatrices that correspond to the difference spaces between the spaces of the finer level and the coarser level. The main idea is to split the matrix into a sum of two matrices, with one reflecting its lower frequency and the other reflecting its higher frequency. We are required to choose the splitting in such a way that the inverse of the lower-frequency matrix either has an explicit form or can easily be computed with a lower computational cost.

In this chapter we introduce the MAM and MIM and provide a complete analysis of their convergence and stability.

Multilevel augmentation methods

In this section, we describe a general setting of the MAM for solving operator equations. This method is based on a standard approximation method at a coarse level and updates the resulting approximate solutions by adding details corresponding to higher levels in a direct sum decomposition. We prove that this method provides the same order of convergence as the original approximation method.

Multilevel augmentation methods for solving operator equations

We begin with a description of the general setup for the operator equations under consideration.