The auxiliary space method and optimal multigrid preconditioning techniques for unstructured grids. (English) Zbl 0857.65129

For the numerical solution of elliptic boundary value problems discretized by finite element schemes on unstructured grids the author develops an abstract framework of the auxiliary space method. This is an optimal preconditioning technique that results from the proper combination of an appropriate smoother and a structured auxiliary grid and can be interpreted as a two-level nonnested multigrid preconditioner. Examples include the use of a
– nested coarse grid space as an auxiliary space,
– lower-order element as an auxiliary space for a higher-order element,
– conforming element as an auxiliary space for a nonconforming element.


65N55 Multigrid methods; domain decomposition for boundary value problems involving PDEs
35J25 Boundary value problems for second-order elliptic equations
65F35 Numerical computation of matrix norms, conditioning, scaling
65F10 Iterative numerical methods for linear systems
65N30 Finite element, Rayleigh-Ritz and Galerkin methods for boundary value problems involving PDEs
Full Text: DOI


[1] Bank, R., Xu, J.: An algorithms for coarsening unstructured meshes. Numer Math. (to appear). · Zbl 0857.65034
[2] Bramble, J. H.: Multigrid methods. Pitman Research Notes in Mathematical Sciences, Vol. 294. Essex: Longman 1993. · Zbl 0786.65094
[3] Bramble, J. H., Pasciak, J. E.: New estimates for multilevel algorithms including the V cycle. Math. Comp.60, 447–471 (1993). · Zbl 0783.65081
[4] Bramble, J. H., Pasciak, J. E. Xu, J.: Parallel multilevel preconditioners. Math. Comp.55, 1–22 (1990). · Zbl 0703.65076
[5] Bramble, J. H., Pasciak, J. E. Xu, J.: The analysis of multigrid algorithms with nonnested spaces or noninherited quadratic forms. Math. Comp.56, 1–34 (1991). · Zbl 0718.65081
[6] Bramble, J. H., Xu, J.: Some estimates for a weightedl 2 projection. Math. Comp.56, 463–476 (1991). · Zbl 0722.65057
[7] Brandt, A.: Multi-level adaptive solutions to boundary-value problems. Math. Comp.31, 333–390 (1977). · Zbl 0373.65054
[8] Brenner, S. C.: Two-level additive schwarz preconditioners for nonconforming finite element methods (preprint). · Zbl 0859.65124
[9] Brenner, S. C.: An optimal order nonconforming multigrid method for the biharmonic equation. SIAM J. Numer. Anal.26, 1124–1138 (1989). · Zbl 0679.65083
[10] Hackbusch, W.: Multigrid methods and applications Vol. 4. Computational mathematics. Berlin Heidelberg New York: Springer 1985. · Zbl 0595.65106
[11] Kornhuber, R., Yserentatn, H.: Multilevel methods for elliptic problems on domains not resolved by the coarse grid. In: Domain Decomposition Methods in Science and Engineering. Proceedings of the Seventh International Conference on Domain Decomposition, October 27–30, 1993, The Pennsylvania State University (Keyes, D. E., Xu, J., eds.). Providence: AMS 1995.
[12] McCormick, S. F.: Multilevel adaptive methods for partial differential equations. Frontiers in Applied Mathematics, Vol. 6., Philadelphia: SIAM 1989. · Zbl 0707.65080
[13] Nepomnyaschikh, S. V.: Mesh theorems of traces, normalizations of function traces and their inversion. Sov. J. Numer. Anal. Math. Modeling6, 1–25 (1991). · Zbl 0816.65097
[14] Nepomnyaschikh, S. V.: Decomposition and fictitious domains methods for elliptic boundary value problems. In: Fifth International Symposium on Domain Decomposition Methods for Partial Differential Equations (Keyes, D. E., Chan, T. F., Meurant, G., Scroggs, J. S., Voigt, R. G., eds.), pp. 62–72. Philadelphia: SIAM 1992. · Zbl 0770.65089
[15] Peisker, P., Braess, D.: A conjugate gradient method and a multigrid method for Morley’s finite element approximation of the biharmonic equation. Numer. Math.50, 567–586 (1987). · Zbl 0595.65113
[16] Raviart, P.-A., Thomas, J. M.: Primal hybrid finite element methods for 2nd order elliptic equations. Math. Comp.31, 391–413, 1977. · Zbl 0364.65082
[17] Smith, B., Chan, T., Zou, J.: Overlapping schwarz methods on unstructured meshes using non-matching coarse grids. Technical Report 94-8, Dept. of Math, UCLA, Feb. 1994. · Zbl 0879.65082
[18] Xu, J.: Theory of multilevel methods. PhD thesis, Cornell University, 1989.
[19] Xu, J.: Convergence estimates for some multigrid algorithms. In: Third International Symposium of Domain Decomposition Methods for Partial Differential Equations (Chan, T. F., Glowinski, R., Périaux, J., Widlund, O. B., eds.), pp. 174–187. Philadelphia: SIAM 1990.
[20] Xu, J.: Iterative methods by space decomposition and subspace correction. SIAM Rev.34, 581–613 (1992). · Zbl 0788.65037
[21] Xu, J.: Multigrid and domain decomposition methods. In: Numerical analysis in applied sciences (Cai, W., Shi, Z., Shu, J., Xu, J., eds.). Singapore: Science Press, 1995.
[22] Zhang, S.: Optimal order non-nested multigrid methods for solving finite element equations I–III. Math. Comp., 1990, 1991, 1994.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.