Research Group of Prof. Dr. M. Griebel
Institute for Numerical Simulation
next up previous
Next: Numerical examples Up: ghbmg-cd Previous: ghbmg-cd


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:

$\displaystyle Tu :=-\Delta u+\vec{b}\cdot\nabla u=f\,\,$ in $\displaystyle \Omega:=\,]0,1[^2$    and$\displaystyle \quad u=0\,\,$ on $\displaystyle \partial\Omega.$ (1.1)

We allow for a convective vector field $ \vec{b}=(b_1,b_2)$ with large $ {{\cal L}^{\infty}(\Omega)}$-norm and for $ \vec{b}$ to vary within a wide range. Problem (1.1) can variationally be formulated as

Find $\displaystyle u\in{\cal H}^1_0(\Omega):\quad a(u,v)=(f,v)_{{\cal L}^2(\Omega)}\quad\forall v\in{\cal H}^1_0(\Omega).$ (1.2)

Under suitable assumptions on $ \vec{b}$, the bilinear-form $ a(u,v):=\int_{\Omega}\nabla u \cdot \nabla v+b_1(\partial_x u) v+b_2(\partial_y u)v\,dxdy$ is elliptic and the Lax-Milgam lemma [9] thus implies the existence of a unique solution to (1.2) for $ f\in{\cal H}^{-1}(\Omega)$. The continuous problem leads after some suitable discretization [21,33], e.g. by a variational Petrov-Galerkin method with trial and test spaces $ {\cal V}_0$ and $ {\cal S}_0$, to a large sparse (usually) non-symmetric system of linear equations

$\displaystyle T_0u_0=f_0.$ (1.3)

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 The hierarchical basis multigrid method (HBMG) [4,8], which is based on the hierarchical decomposition of the space of (bi-)linear splines, has been proven to be an efficient solver for nicely elliptic problems. However, for convection-diffusion equations it is well known that standard HBMG suffers from both of the above obstructions. It neither leads to an optimal (w.r.t. mesh size) nor to a robust method when applied to the discrete singularly perturbed problems - either directly or as a preconditioner for a non-symmetric iterative solver. Here, the performance is still strongly dependent on the coefficients of the differential equation (e.g. strength of convection) [5]. A main reason for the lack of robustness is that the coarse-grid operators tend to be increasingly unstable when the convective term starts to dominate on coarser scales just like in standard multigrid methods. The hereby computed subspace-``corrections'' finally destroy the convergence of the iteration [5,18,42]. Furthermore, the criterion of ``robust smoothers'' from robust multigrid strategies cannot be met since the employed hierarchical smoothers will not degenerate in the limit case of pure convection to a direct solver for each level [21]. Hierarchical smoothers compute corrections only for parts of the unknowns.

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 $ {\cal V}_0$ and $ {\cal S}_0$ 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.

next up previous
Next: Numerical examples Up: ghbmg-cd Previous: ghbmg-cd
Frank Kiefer