Introduction

We consider the efficient solution of large sparse non-symmetric linear systems that arise from discretizations of the following singularly perturbed stationary convection-diffusion problem with homogeneous Dirichlet boundary conditions on the unit-square:

We allow for a convective vector field with large -norm and for to vary within a wide range. Problem (1.1) can variationally be formulated as

Under suitable assumptions on , the bilinear-form is elliptic and the Lax-Milgam lemma [9] thus implies the existence of a unique solution to (1.2) for . The continuous problem leads after some suitable discretization [21,33], e.g. by a variational Petrov-Galerkin method with trial and test spaces and , to a large sparse (usually) non-symmetric system of linear equations

Often these linear systems are solved by non-symmetric iterative methods [22,33,35]. But here, the following two common major difficulties arise: The convergence

- deteriorates with decreasing mesh size of the underlying mesh and
- is strongly dependent on the convective vector field .

Recently there have been several attempts to improve on the robustness of the corresponding algorithm. One approach introduces generalized hierarchical bases which are better suited to the problem at hand [6,14,29]. Here, one benefits from an intimate connection between hierarchical bases and an approximate Gaussian elimination [7,18], which implicitly leads to problem-adapted and physically meaningful coarse-grid operators. However, these methods still suffer from the bad stability properties (now w.r.t. mesh size) of the underlying hierarchical splittings and the conceptual weakness of hierarchical smoothers. From our numerical examples we see that the convergence rates of the corresponding iterations even seem to deteriorate when the perturbation increases.

Another approach constructs stabilized algorithms (w.r.t. mesh size) that use recursively defined polynomial Schur-complement approximations to improve on the coarse-grid corrections of the classical HBMG method [2,3]. They may be interpreted as HBMG algorithms with a more general cyclic structure than the standard V-cycle. Indeed, one obtains the same effect from a hierarchical W-cycle, which can be implemented with linear complexity and also leads to an optimal method [18,24].

Finally, (pre-)wavelet splittings of the underlying function spaces allow for efficient
algorithms which can be viewed as generalized HBMG methods [24,27,40]. They can
also be interpreted as ordinary multigrid methods which use a special kind of *
multiscale smoother* [24] and show an optimal convergence behavior for the
respective non-perturbed equations similar to classical multigrid [38]. From a
theoretical point of view this is due to the enhanced stability properties of the
corresponding splittings [11,26]. From the multigrid interpretation the reason is
the stronger effect of the respective smoothing iteration compared to the hierarchical
one. However, (pre-)wavelet based multiscale smoothers still compute corrections only for
parts of the unknowns due to the direct subspace decompositions. Hence, * robust*
multiscale smoothers are on principle out of reach.

A means left to construct robust solvers based on direct splittings of the underlying function spaces is the choice of the multiscale decompositions itself. In our approach we start from a rather general Petrov-Galerkin multiscale concept. We apply problem-dependent coarsening strategies known from robust multigrid techniques (matrix-dependent prolongations, algebraic coarsening) [1,10,15,16,18,23,34,36,42,43] together with special (pre-)wavelet-like and hierarchical multiscale decompositions of the trial and test spaces and on the finest grid. The main idea to overcome the difficulties mentioned above is to choose one complement space hierarchically (to approximately eliminate the coarse-grid unknowns from the transformed equations for the fine-without-coarse-grid degrees of freedom and thus to obtain physically meaningful coarse-grid operators) and the other one wavelet-like (to stabilize the multiscale setting w.r.t. mesh size and to strengthen the smoother). Our numerical results show that by this choice generalized HBMG methods can be constructed which result in robust yet efficient solvers.