How far could one go in developing robust multiscale techniques for convection-diffusion problems exploiting direct decompositions of the discretization spaces?
According to the three major problems which have been raised in the introduction with respect to the above question (dependence of , dependence of and stability of the coarse-grid problems involved) our answer consists of three main ingredients.
First, the problem-dependent choice of the prolongation operators within our Petrov-Galerkin multiscale approach is indispensable to obtain physically reasonable coarse-grid problems, which are used for the multiscale solution process. Considering the challenging test example of a circular convection we even had to resort to techniques from AMG. Second, starting from hierarchical decompositions of the trial and test side a change to a wavelet-like complement basis on one side is necessary to enhance the stability of the decomposition with respect to mesh size and to repair (at least to some extend) the defects of the hierarchical smoothers. This is even true for the essentially one-dimensional problem . However note that the resulting multiscale smoothers still do not fulfill the criterion of robust smoothers from robust multigrid. The third reason why the proposed method works, is the combination of the hierarchical decomposition on the test side along with the problem-dependent coarsening on the trial side. As we have seen this is equivalent to a decoupling of the transformed linear system for one-dimensional problems. In the two-dimensional case the decoupling relation from this choice is only approximate. Further experiments showed that it is nevertheless necessary for non-symmetric problems.
By a Petrov-Galerkin multiscale concept it is possible to bring together all of the above ideas which are of course closely intertwined. Therefore, our approach extends by far other existing methods which also rely on direct subspace decompositions, e.g. those in [2,3,17,29,30]. The wavelet based direct solver in  does not work for our singularly perturbed problems since it does not apply problem adapted multiscale decompositions. Many other traditional wavelet approaches for solving partial differential equations face the same difficulty [12,13,17,28,32,39]. This is also true for the AMLI method which starts from classical hierarchical decompositions and employs a stabilization by inner iterations to guarantee optimal preconditioning. The generalized hierarchical basis multigrid methods in [6,14] are based on matrix dependent prolongations and hierarchical decompositions within a Petrov-Galerkin multiscale setting. However, they suffer from the principal weakness of the corresponding hierarchical smoothers which can also be seen from the numerical results in . Although the method of approximate cyclic reduction [29,30] applies algebraically defined hierarchical subspace decompositions, the quality of the resulting preconditioner still seems to be slightly dependent on the mesh size of the finest grid. Our new AMGlet approach, which is also based on purely algebraical principles, provides here a simple remedy. Furthermore, with this approach we are able to leave the context of tensor product constructions which only work well for non-separable problems. This paths the way from model problems to problems which are relevant in practice.
We think that due to all the interrelations and especially due to the conceptual weakness of the corresponding multiscale smoothers it is much harder to design robust multiscale methods starting from direct decompositions than from a true generating system approach as for example in multigrid [19,20]. This is true, even if one has a clear separation of the correction steps by direct decompositions, which might be advantageous for developing a satisfying convergence theory in the future.
Acknowledgment. We thank M. A. Schweitzer for stimulating discussions and for providing us his AMG-code.